GVN.cpp revision e5ffa900f8cf486fae4f542d72d84e6bab0129ae
1710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov//===- GVN.cpp - Eliminate redundant values and loads ------------===// 26091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer// 36091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer// The LLVM Compiler Infrastructure 46091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 76091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer// 86091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer//===----------------------------------------------------------------------===// 927107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling// 1027107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling// This pass performs global value numbering to eliminate fully redundant 1127107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling// instructions. It also performs simple dead load elimination. 1227107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling// 1327107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling//===----------------------------------------------------------------------===// 146091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer 156091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer#define DEBUG_TYPE "gvn" 16674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#include "llvm/Transforms/Scalar.h" 17674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#include "llvm/BasicBlock.h" 186091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer#include "llvm/Constants.h" 19d509d0b532ec2358b3f341d4a4cd1411cb8b5db2Chris Lattner#include "llvm/DerivedTypes.h" 200319888773b36dd61d7d2283cb9a26cac1e5abe8Bill Wendling#include "llvm/Function.h" 213467e30edf63b6d8a8d446186674ba9e4b7885a9Bill Wendling#include "llvm/IntrinsicInst.h" 2222bd64173981bf1251c4b3bfc684207340534ba3Bill Wendling#include "llvm/Instructions.h" 23ea59f896a672c2e1ef9f02277bce60257aa60989Bill Wendling#include "llvm/ParameterAttributes.h" 2458d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner#include "llvm/Value.h" 256091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer#include "llvm/ADT/BitVector.h" 266091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer#include "llvm/ADT/DenseMap.h" 27d426a642a23a234547cbc7061f5bfec157673249Bill Wendling#include "llvm/ADT/DepthFirstIterator.h" 28702cc91aa1bd41540e8674921ae7ac89a4ff061fBill Wendling#include "llvm/ADT/SmallPtrSet.h" 29f6670729aabc1fab85238d2b306a1c1767a807bbBill Wendling#include "llvm/ADT/SmallVector.h" 30817abdd8b055059e5930a15704b9f52da4236456Bill Wendling#include "llvm/ADT/Statistic.h" 31817abdd8b055059e5930a15704b9f52da4236456Bill Wendling#include "llvm/Analysis/Dominators.h" 326dc3781d44e56f0addf28b06232a50f3f9e6b1afBill Wendling#include "llvm/Analysis/AliasAnalysis.h" 332c79ecbd704c656178ffa43d5a58ebe3ca188b40Bill Wendling#include "llvm/Analysis/MemoryDependenceAnalysis.h" 34ad9a9e15595bc9d5ba1ed752caf8572957f77a3dDuncan Sands#include "llvm/Support/CFG.h" 35ad9a9e15595bc9d5ba1ed752caf8572957f77a3dDuncan Sands#include "llvm/Support/CommandLine.h" 361d3dcfe4246b4d45fa78a8dfd0a11c7fff842c15Bill Wendling#include "llvm/Support/Compiler.h" 3727107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling#include "llvm/Support/Debug.h" 3827107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling#include "llvm/Support/GetElementPtrTypeIterator.h" 391d3dcfe4246b4d45fa78a8dfd0a11c7fff842c15Bill Wendling#include "llvm/Target/TargetData.h" 401d3dcfe4246b4d45fa78a8dfd0a11c7fff842c15Bill Wendling#include <list> 411d3dcfe4246b4d45fa78a8dfd0a11c7fff842c15Bill Wendlingusing namespace llvm; 42034b94b17006f51722886b0f2283fb6fb19aca1fBill Wendling 436765834754cbb3cb0f15b4b15e98c5e73fa50066Bill WendlingSTATISTIC(NumGVNInstr, "Number of instructions deleted"); 441d3dcfe4246b4d45fa78a8dfd0a11c7fff842c15Bill WendlingSTATISTIC(NumGVNLoad, "Number of loads deleted"); 4573dee180c836270644dfa7d90f9c5ba877567999Bill WendlingSTATISTIC(NumMemSetInfer, "Number of memsets inferred"); 46f3d1500ab2c7364d3d0fb73a7e1b8c6339ab48b1Bill Wendling 4773dee180c836270644dfa7d90f9c5ba877567999Bill Wendlingnamespace { 4873dee180c836270644dfa7d90f9c5ba877567999Bill Wendling cl::opt<bool> 4973dee180c836270644dfa7d90f9c5ba877567999Bill Wendling FormMemSet("form-memset-from-stores", 50f3d1500ab2c7364d3d0fb73a7e1b8c6339ab48b1Bill Wendling cl::desc("Transform straight-line stores to memsets"), 5173dee180c836270644dfa7d90f9c5ba877567999Bill Wendling cl::init(true), cl::Hidden); 5211d00420e42ba88c3b48cab997965a7be79315e2Bill Wendling} 5311d00420e42ba88c3b48cab997965a7be79315e2Bill Wendling 54f3d1500ab2c7364d3d0fb73a7e1b8c6339ab48b1Bill Wendling//===----------------------------------------------------------------------===// 5511d00420e42ba88c3b48cab997965a7be79315e2Bill Wendling// ValueTable Class 5611d00420e42ba88c3b48cab997965a7be79315e2Bill Wendling//===----------------------------------------------------------------------===// 5711d00420e42ba88c3b48cab997965a7be79315e2Bill Wendling 5811d00420e42ba88c3b48cab997965a7be79315e2Bill Wendling/// This class holds the mapping between values and value numbers. It is used 5911d00420e42ba88c3b48cab997965a7be79315e2Bill Wendling/// as an efficient mechanism to determine the expression-wise equivalence of 6011d00420e42ba88c3b48cab997965a7be79315e2Bill Wendling/// two values. 61629fb82419d9bfff6ae475363bcce66192dfcc8eBill Wendlingnamespace { 625a0eeb5a9d727940b1dbe8dff6e9aa292ada0f6aBill Wendling struct VISIBILITY_HIDDEN Expression { 63480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 64480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 65480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 666765834754cbb3cb0f15b4b15e98c5e73fa50066Bill Wendling ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 67f6670729aabc1fab85238d2b306a1c1767a807bbBill Wendling FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 68480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 69480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 70480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 71480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 729a419f656e278b96e9dfe739cd63c7bff9a4e1fdQuentin Colombet PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, EMPTY, 73480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling TOMBSTONE }; 74480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling 75480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling ExpressionOpcode opcode; 76480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling const Type* type; 7767ae13575900e8efd056672987249fd0adbf5e73James Molloy uint32_t firstVN; 78480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling uint32_t secondVN; 79480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling uint32_t thirdVN; 80480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling SmallVector<uint32_t, 4> varargs; 813a106e60366a51b4594ec303ff8dbbc58913227fBill Wendling Value* function; 82480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling 83480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling Expression() { } 84480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling Expression(ExpressionOpcode o) : opcode(o) { } 85480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling 86480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling bool operator==(const Expression &other) const { 87480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling if (opcode != other.opcode) 88480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling return false; 89480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling else if (opcode == EMPTY || opcode == TOMBSTONE) 90480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling return true; 916765834754cbb3cb0f15b4b15e98c5e73fa50066Bill Wendling else if (type != other.type) 926765834754cbb3cb0f15b4b15e98c5e73fa50066Bill Wendling return false; 93f6670729aabc1fab85238d2b306a1c1767a807bbBill Wendling else if (function != other.function) 94480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling return false; 95480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling else if (firstVN != other.firstVN) 96114baee1fa017daefad2339c77b45b9ca3d79a41Bill Wendling return false; 97480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling else if (secondVN != other.secondVN) 98ab39afa9d9b99c61842c8e3d0eb706bd16efdcf3Kostya Serebryany return false; 99ab39afa9d9b99c61842c8e3d0eb706bd16efdcf3Kostya Serebryany else if (thirdVN != other.thirdVN) 100480b1b28ea6fc1bb5c78d99472df624cfd3fce47Bill Wendling return false; 1010319888773b36dd61d7d2283cb9a26cac1e5abe8Bill Wendling else { 1020319888773b36dd61d7d2283cb9a26cac1e5abe8Bill Wendling if (varargs.size() != other.varargs.size()) 1033a4779a9211281a1d0c27c97037342329035a185NAKAMURA Takumi return false; 1043a4779a9211281a1d0c27c97037342329035a185NAKAMURA Takumi 1056f78fbbc630d2b86fb752574f5ad74473f57dfb1Chandler Carruth for (size_t i = 0; i < varargs.size(); ++i) 1066f78fbbc630d2b86fb752574f5ad74473f57dfb1Chandler Carruth if (varargs[i] != other.varargs[i]) 1076765834754cbb3cb0f15b4b15e98c5e73fa50066Bill Wendling return false; 1086765834754cbb3cb0f15b4b15e98c5e73fa50066Bill Wendling 10927107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling return true; 11027107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling } 111d426a642a23a234547cbc7061f5bfec157673249Bill Wendling } 11227107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling 1132c79ecbd704c656178ffa43d5a58ebe3ca188b40Bill Wendling bool operator!=(const Expression &other) const { 114c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling if (opcode != other.opcode) 115c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling return true; 116c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling else if (opcode == EMPTY || opcode == TOMBSTONE) 117c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling return false; 118c08a5ef6581f2c7550e92d31f63cd65ec29c39e0Bill Wendling else if (type != other.type) 1198c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling return true; 1208c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling else if (function != other.function) 1218c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling return true; 1222c79ecbd704c656178ffa43d5a58ebe3ca188b40Bill Wendling else if (firstVN != other.firstVN) 123c08a5ef6581f2c7550e92d31f63cd65ec29c39e0Bill Wendling return true; 124c08a5ef6581f2c7550e92d31f63cd65ec29c39e0Bill Wendling else if (secondVN != other.secondVN) 125c08a5ef6581f2c7550e92d31f63cd65ec29c39e0Bill Wendling return true; 126c08a5ef6581f2c7550e92d31f63cd65ec29c39e0Bill Wendling else if (thirdVN != other.thirdVN) 127c08a5ef6581f2c7550e92d31f63cd65ec29c39e0Bill Wendling return true; 128c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling else { 129c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling if (varargs.size() != other.varargs.size()) 130c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling return true; 131c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling 1328c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling for (size_t i = 0; i < varargs.size(); ++i) 1338c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling if (varargs[i] != other.varargs[i]) 1348c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling return true; 1358c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling 1368c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling return false; 1378c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling } 1388c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling } 1398c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling }; 1408c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling 1418c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling class VISIBILITY_HIDDEN ValueTable { 142eddab1550ee10cce3bb26a26e88529cb19451aa3NAKAMURA Takumi private: 143eddab1550ee10cce3bb26a26e88529cb19451aa3NAKAMURA Takumi DenseMap<Value*, uint32_t> valueNumbering; 144eddab1550ee10cce3bb26a26e88529cb19451aa3NAKAMURA Takumi DenseMap<Expression, uint32_t> expressionNumbering; 14564754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling AliasAnalysis* AA; 14664754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling 14764754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling uint32_t nextValueNumber; 1488c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling 1498c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 1508c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling Expression::ExpressionOpcode getOpcode(CmpInst* C); 1516dc3781d44e56f0addf28b06232a50f3f9e6b1afBill Wendling Expression::ExpressionOpcode getOpcode(CastInst* C); 1528c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling Expression create_expression(BinaryOperator* BO); 1538c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling Expression create_expression(CmpInst* C); 1548c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling Expression create_expression(ShuffleVectorInst* V); 1558c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling Expression create_expression(ExtractElementInst* C); 1568c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling Expression create_expression(InsertElementInst* V); 1578c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling Expression create_expression(SelectInst* V); 1588c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling Expression create_expression(CastInst* C); 1598c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling Expression create_expression(GetElementPtrInst* G); 1608c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling Expression create_expression(CallInst* C); 1618c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling public: 1628c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling ValueTable() : nextValueNumber(1) { } 1636dc3781d44e56f0addf28b06232a50f3f9e6b1afBill Wendling uint32_t lookup_or_add(Value* V); 1641d3dcfe4246b4d45fa78a8dfd0a11c7fff842c15Bill Wendling uint32_t lookup(Value* V) const; 165ef99fe8efaa6cb74c66e570a6ef467debca92911Bill Wendling void add(Value* V, uint32_t num); 166e66f3d3ba0ea9f82f65a29c47fc37e997cbf0aceBill Wendling void clear(); 167ef99fe8efaa6cb74c66e570a6ef467debca92911Bill Wendling void erase(Value* v); 1681d3dcfe4246b4d45fa78a8dfd0a11c7fff842c15Bill Wendling unsigned size(); 169943c29135e03e55f9a5dab393786171a4a536482Bill Wendling void setAliasAnalysis(AliasAnalysis* A) { AA = A; } 170e66f3d3ba0ea9f82f65a29c47fc37e997cbf0aceBill Wendling uint32_t hash_operand(Value* v); 17130b483c94001927b3593ed200e823104bab51660Bill Wendling }; 172c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling} 173c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling 174b29ce26ea60f7516c853318ffbfc107fde9ad897Bill Wendlingnamespace llvm { 175c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendlingtemplate <> struct DenseMapInfo<Expression> { 1768c74ecfbddabe89e150abff4fdff0a27108874b9Bill Wendling static inline Expression getEmptyKey() { 1772d5be6c313c0f9e23e56620fa8f8ae8d9b539bf0Bill Wendling return Expression(Expression::EMPTY); 1782d5be6c313c0f9e23e56620fa8f8ae8d9b539bf0Bill Wendling } 1792d5be6c313c0f9e23e56620fa8f8ae8d9b539bf0Bill Wendling 180c08a5ef6581f2c7550e92d31f63cd65ec29c39e0Bill Wendling static inline Expression getTombstoneKey() { 1813467e30edf63b6d8a8d446186674ba9e4b7885a9Bill Wendling return Expression(Expression::TOMBSTONE); 1823467e30edf63b6d8a8d446186674ba9e4b7885a9Bill Wendling } 183bb08593980b16fbd9758da6ca4fa9c7964f2f926Bill Wendling 184bb08593980b16fbd9758da6ca4fa9c7964f2f926Bill Wendling static unsigned getHashValue(const Expression e) { 185bb08593980b16fbd9758da6ca4fa9c7964f2f926Bill Wendling unsigned hash = e.opcode; 186827cde1c8319e51463007078a7ce3660ebc93036Duncan Sands 187827cde1c8319e51463007078a7ce3660ebc93036Duncan Sands hash = e.firstVN + hash * 37; 188e66f3d3ba0ea9f82f65a29c47fc37e997cbf0aceBill Wendling hash = e.secondVN + hash * 37; 18927107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling hash = e.thirdVN + hash * 37; 19016274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling 19116274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling hash = ((unsigned)((uintptr_t)e.type >> 4) ^ 19216274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling (unsigned)((uintptr_t)e.type >> 9)) + 19316274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling hash * 37; 19416274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling 19516274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), 19616274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling E = e.varargs.end(); I != E; ++I) 19716274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling hash = *I + hash * 37; 19816274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling 19916274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling hash = ((unsigned)((uintptr_t)e.function >> 4) ^ 20016274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling (unsigned)((uintptr_t)e.function >> 9)) + 20116274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling hash * 37; 20216274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling 20316274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling return hash; 20416274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling } 20516274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling static bool isEqual(const Expression &LHS, const Expression &RHS) { 20616274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling return LHS == RHS; 20716274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling } 20816274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling static bool isPod() { return true; } 20916274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling}; 210c3662eeaa4a1a4061fc6d5c81e3eed48c5d9da26Bill Wendling} 211c3662eeaa4a1a4061fc6d5c81e3eed48c5d9da26Bill Wendling 212c3662eeaa4a1a4061fc6d5c81e3eed48c5d9da26Bill Wendling//===----------------------------------------------------------------------===// 213c3662eeaa4a1a4061fc6d5c81e3eed48c5d9da26Bill Wendling// ValueTable Internal Functions 214c3662eeaa4a1a4061fc6d5c81e3eed48c5d9da26Bill Wendling//===----------------------------------------------------------------------===// 215c3662eeaa4a1a4061fc6d5c81e3eed48c5d9da26Bill WendlingExpression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) { 21699faa3b4ec6d03ac7808fe4ff3fbf3d04e375502Bill Wendling switch(BO->getOpcode()) { 21707aae2e7d58fe23e370e0cbb9e1a3def99434c36Bill Wendling default: // THIS SHOULD NEVER HAPPEN 21807aae2e7d58fe23e370e0cbb9e1a3def99434c36Bill Wendling assert(0 && "Binary operator with unknown opcode?"); 21907aae2e7d58fe23e370e0cbb9e1a3def99434c36Bill Wendling case Instruction::Add: return Expression::ADD; 22007aae2e7d58fe23e370e0cbb9e1a3def99434c36Bill Wendling case Instruction::Sub: return Expression::SUB; 22107aae2e7d58fe23e370e0cbb9e1a3def99434c36Bill Wendling case Instruction::Mul: return Expression::MUL; 22207aae2e7d58fe23e370e0cbb9e1a3def99434c36Bill Wendling case Instruction::UDiv: return Expression::UDIV; 223a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case Instruction::SDiv: return Expression::SDIV; 2247d38c109aab8654e63e9071c7d948661f6b58433Bill Wendling case Instruction::FDiv: return Expression::FDIV; 22516274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling case Instruction::URem: return Expression::UREM; 226a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling case Instruction::SRem: return Expression::SREM; 22773dee180c836270644dfa7d90f9c5ba877567999Bill Wendling case Instruction::FRem: return Expression::FREM; 2280976e00fd1cbf4128daeb72efd8957d00383fda9Bill Wendling case Instruction::Shl: return Expression::SHL; 229ec2589863b32da169240c4fa120ef1e3798615d4Bill Wendling case Instruction::LShr: return Expression::LSHR; 2300976e00fd1cbf4128daeb72efd8957d00383fda9Bill Wendling case Instruction::AShr: return Expression::ASHR; 23173dee180c836270644dfa7d90f9c5ba877567999Bill Wendling case Instruction::And: return Expression::AND; 232606c8e36dfdd28fc589356addd3e2cbb89a32e4dBill Wendling case Instruction::Or: return Expression::OR; 2330976e00fd1cbf4128daeb72efd8957d00383fda9Bill Wendling case Instruction::Xor: return Expression::XOR; 23487e10dfefa94f77937c37b0eb51095540d675cbcBill Wendling } 23587e10dfefa94f77937c37b0eb51095540d675cbcBill Wendling} 2366bdbf061c353295669b6bfc271b948158602d1bcBill Wendling 23787e10dfefa94f77937c37b0eb51095540d675cbcBill WendlingExpression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 2386bdbf061c353295669b6bfc271b948158602d1bcBill Wendling if (isa<ICmpInst>(C)) { 23987e10dfefa94f77937c37b0eb51095540d675cbcBill Wendling switch (C->getPredicate()) { 24087e10dfefa94f77937c37b0eb51095540d675cbcBill Wendling default: // THIS SHOULD NEVER HAPPEN 24187e10dfefa94f77937c37b0eb51095540d675cbcBill Wendling assert(0 && "Comparison with unknown predicate?"); 2426bdbf061c353295669b6bfc271b948158602d1bcBill Wendling case ICmpInst::ICMP_EQ: return Expression::ICMPEQ; 24387e10dfefa94f77937c37b0eb51095540d675cbcBill Wendling case ICmpInst::ICMP_NE: return Expression::ICMPNE; 24487e10dfefa94f77937c37b0eb51095540d675cbcBill Wendling case ICmpInst::ICMP_UGT: return Expression::ICMPUGT; 2457d38c109aab8654e63e9071c7d948661f6b58433Bill Wendling case ICmpInst::ICMP_UGE: return Expression::ICMPUGE; 246ec2589863b32da169240c4fa120ef1e3798615d4Bill Wendling case ICmpInst::ICMP_ULT: return Expression::ICMPULT; 24758d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner case ICmpInst::ICMP_ULE: return Expression::ICMPULE; 248ec2589863b32da169240c4fa120ef1e3798615d4Bill Wendling case ICmpInst::ICMP_SGT: return Expression::ICMPSGT; 249ec2589863b32da169240c4fa120ef1e3798615d4Bill Wendling case ICmpInst::ICMP_SGE: return Expression::ICMPSGE; 250d05204aea4977eaec25e96bc7605a7bb9d806fc0Bill Wendling case ICmpInst::ICMP_SLT: return Expression::ICMPSLT; 251d05204aea4977eaec25e96bc7605a7bb9d806fc0Bill Wendling case ICmpInst::ICMP_SLE: return Expression::ICMPSLE; 252d05204aea4977eaec25e96bc7605a7bb9d806fc0Bill Wendling } 253d05204aea4977eaec25e96bc7605a7bb9d806fc0Bill Wendling } 254710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov assert(isa<FCmpInst>(C) && "Unknown compare"); 25558d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner switch (C->getPredicate()) { 256c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling default: // THIS SHOULD NEVER HAPPEN 25758d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner assert(0 && "Comparison with unknown predicate?"); 258710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ; 25918e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling case FCmpInst::FCMP_OGT: return Expression::FCMPOGT; 2608e47daf2858e980210f3e1f007036b24da342c29Bill Wendling case FCmpInst::FCMP_OGE: return Expression::FCMPOGE; 26128d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling case FCmpInst::FCMP_OLT: return Expression::FCMPOLT; 26232a57958226e369f964a034da2ce7083a1a34297Bill Wendling case FCmpInst::FCMP_OLE: return Expression::FCMPOLE; 2631bbd644301ed4d8a7efd4ceb15f71c56fa914f28Bill Wendling case FCmpInst::FCMP_ONE: return Expression::FCMPONE; 26458d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner case FCmpInst::FCMP_ORD: return Expression::FCMPORD; 265defaca00b8087d452df2b783250a48a32658a910Bill Wendling case FCmpInst::FCMP_UNO: return Expression::FCMPUNO; 266defaca00b8087d452df2b783250a48a32658a910Bill Wendling case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ; 267defaca00b8087d452df2b783250a48a32658a910Bill Wendling case FCmpInst::FCMP_UGT: return Expression::FCMPUGT; 268defaca00b8087d452df2b783250a48a32658a910Bill Wendling case FCmpInst::FCMP_UGE: return Expression::FCMPUGE; 269710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov case FCmpInst::FCMP_ULT: return Expression::FCMPULT; 270e4e85f17564c28cd571dda30146c3f310521acf0Bill Wendling case FCmpInst::FCMP_ULE: return Expression::FCMPULE; 271e4e85f17564c28cd571dda30146c3f310521acf0Bill Wendling case FCmpInst::FCMP_UNE: return Expression::FCMPUNE; 272e4e85f17564c28cd571dda30146c3f310521acf0Bill Wendling } 273e4e85f17564c28cd571dda30146c3f310521acf0Bill Wendling} 274e4e85f17564c28cd571dda30146c3f310521acf0Bill Wendling 27518e7211068c9d2c6204512f9c468ee179818a4b6Bill WendlingExpression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) { 2768246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling switch(C->getOpcode()) { 27718e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling default: // THIS SHOULD NEVER HAPPEN 2788246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling assert(0 && "Cast operator with unknown opcode?"); 2798246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling case Instruction::Trunc: return Expression::TRUNC; 2808246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling case Instruction::ZExt: return Expression::ZEXT; 2818246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling case Instruction::SExt: return Expression::SEXT; 2828246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling case Instruction::FPToUI: return Expression::FPTOUI; 2838246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling case Instruction::FPToSI: return Expression::FPTOSI; 2848246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling case Instruction::UIToFP: return Expression::UITOFP; 2858246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling case Instruction::SIToFP: return Expression::SITOFP; 286710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov case Instruction::FPTrunc: return Expression::FPTRUNC; 28758d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner case Instruction::FPExt: return Expression::FPEXT; 288c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling case Instruction::PtrToInt: return Expression::PTRTOINT; 28958d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner case Instruction::IntToPtr: return Expression::INTTOPTR; 29018e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling case Instruction::BitCast: return Expression::BITCAST; 29185b3fbecdfe934ac7519a8831c4bd262cba99d12Bill Wendling } 29285b3fbecdfe934ac7519a8831c4bd262cba99d12Bill Wendling} 29385b3fbecdfe934ac7519a8831c4bd262cba99d12Bill Wendling 29418e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendlinguint32_t ValueTable::hash_operand(Value* v) { 29528d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling if (CallInst* CI = dyn_cast<CallInst>(v)) 29619c874638d9478a5d5028854817a5ee72293bb2bDevang Patel if (!AA->doesNotAccessMemory(CI)) 29718e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling return nextValueNumber++; 2983fc4b96b503fa202411317684a2ba02e41e43072Bill Wendling 29919c874638d9478a5d5028854817a5ee72293bb2bDevang Patel return lookup_or_add(v); 30018e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling} 301c5f1bc88a2eb7ad9ff924ca90cf88494e5f947b9Bill Wendling 302710632d07b13609444626367bebd34c0af3acb6aMikhail GlushenkovExpression ValueTable::create_expression(CallInst* C) { 303831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling Expression e; 30419d815c04fde6b7b53c2b542813157edfa213842Bill Wendling 305831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling e.type = C->getType(); 306831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling e.firstVN = 0; 30719d815c04fde6b7b53c2b542813157edfa213842Bill Wendling e.secondVN = 0; 308831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling e.thirdVN = 0; 309c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling e.function = C->getCalledFunction(); 310c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling e.opcode = Expression::CALL; 311c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling 312c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end(); 31349f6060f16aec4024d644a6ec4ddd3de9b3e8821Bill Wendling I != E; ++I) 31419d815c04fde6b7b53c2b542813157edfa213842Bill Wendling e.varargs.push_back(hash_operand(*I)); 3158e47daf2858e980210f3e1f007036b24da342c29Bill Wendling 316831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling return e; 31719d815c04fde6b7b53c2b542813157edfa213842Bill Wendling} 318831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling 319831737d329a727f53a1fb0572f7b7a8127208881Bill WendlingExpression ValueTable::create_expression(BinaryOperator* BO) { 320b29ce26ea60f7516c853318ffbfc107fde9ad897Bill Wendling Expression e; 321831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling 32216c4b3cf2943ae2327752cf3de39769d14cfceceBill Wendling e.firstVN = hash_operand(BO->getOperand(0)); 32316c4b3cf2943ae2327752cf3de39769d14cfceceBill Wendling e.secondVN = hash_operand(BO->getOperand(1)); 324f715dbd263149efeb9c684dfdb0637cf84f94399Bill Wendling e.thirdVN = 0; 325f715dbd263149efeb9c684dfdb0637cf84f94399Bill Wendling e.function = 0; 32616c4b3cf2943ae2327752cf3de39769d14cfceceBill Wendling e.type = BO->getType(); 327041221c0972ff575b07f76808c504833d629ae1fChris Lattner e.opcode = getOpcode(BO); 32818e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling 329ec2589863b32da169240c4fa120ef1e3798615d4Bill Wendling return e; 33018e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling} 33118e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling 332ec2589863b32da169240c4fa120ef1e3798615d4Bill WendlingExpression ValueTable::create_expression(CmpInst* C) { 33318e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling Expression e; 334710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov 33558d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner e.firstVN = hash_operand(C->getOperand(0)); 336c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling e.secondVN = hash_operand(C->getOperand(1)); 33758d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner e.thirdVN = 0; 338710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov e.function = 0; 339c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling e.type = C->getType(); 340c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling e.opcode = getOpcode(C); 341c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling 34218e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling return e; 34358d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner} 344ec2589863b32da169240c4fa120ef1e3798615d4Bill Wendling 34558d74910c6b82e622ecbb57d6644d48fec5a5c0fChris LattnerExpression ValueTable::create_expression(CastInst* C) { 346710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov Expression e; 34718e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling 34858d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner e.firstVN = hash_operand(C->getOperand(0)); 349aa57893e84ba7a35948fcaa99812ba88e58f4797Bill Wendling e.secondVN = 0; 35058d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner e.thirdVN = 0; 351710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov e.function = 0; 35218e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling e.type = C->getType(); 35318e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling e.opcode = getOpcode(C); 35418e7211068c9d2c6204512f9c468ee179818a4b6Bill Wendling 35558d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner return e; 356710632d07b13609444626367bebd34c0af3acb6aMikhail Glushenkov} 357e1f95db4803a48a30fc2a1d5868281a87a36fb85Bill Wendling 3583e3e789aede6ec38d39c95d88ad4e8634d5a259bBill WendlingExpression ValueTable::create_expression(ShuffleVectorInst* S) { 359e1f95db4803a48a30fc2a1d5868281a87a36fb85Bill Wendling Expression e; 3608e47daf2858e980210f3e1f007036b24da342c29Bill Wendling 3618e47daf2858e980210f3e1f007036b24da342c29Bill Wendling e.firstVN = hash_operand(S->getOperand(0)); 3628e47daf2858e980210f3e1f007036b24da342c29Bill Wendling e.secondVN = hash_operand(S->getOperand(1)); 363f3d1500ab2c7364d3d0fb73a7e1b8c6339ab48b1Bill Wendling e.thirdVN = hash_operand(S->getOperand(2)); 36458d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner e.function = 0; 3654f859aa532dbf061736f9c23e0d0882b5cdfe566Reid Spencer e.type = S->getType(); 366a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling e.opcode = Expression::SHUFFLE; 367a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 36816274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling return e; 36916274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling} 37016274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling 37116274258d16342a2f91aaa3690b78ce74e4105f1Bill WendlingExpression ValueTable::create_expression(ExtractElementInst* E) { 37216274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling Expression e; 37316274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling 374c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling e.firstVN = hash_operand(E->getOperand(0)); 37516274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling e.secondVN = hash_operand(E->getOperand(1)); 37616274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling e.thirdVN = 0; 37716274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling e.function = 0; 37816274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling e.type = E->getType(); 379c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling e.opcode = Expression::EXTRACT; 38016274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling 38116274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling return e; 38216274258d16342a2f91aaa3690b78ce74e4105f1Bill Wendling} 383c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling 38416274258d16342a2f91aaa3690b78ce74e4105f1Bill WendlingExpression ValueTable::create_expression(InsertElementInst* I) { 385c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling Expression e; 386c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling 387c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling e.firstVN = hash_operand(I->getOperand(0)); 388c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling e.secondVN = hash_operand(I->getOperand(1)); 389a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling e.thirdVN = hash_operand(I->getOperand(2)); 390a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling e.function = 0; 391a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling e.type = I->getType(); 392a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling e.opcode = Expression::INSERT; 393a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 394a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return e; 395ea59f896a672c2e1ef9f02277bce60257aa60989Bill Wendling} 396a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 397a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill WendlingExpression ValueTable::create_expression(SelectInst* I) { 398a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling Expression e; 399a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 400f9271ea159b97e2febedcf095c3c4122cb24d077Bill Wendling e.firstVN = hash_operand(I->getCondition()); 401f9271ea159b97e2febedcf095c3c4122cb24d077Bill Wendling e.secondVN = hash_operand(I->getTrueValue()); 402a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling e.thirdVN = hash_operand(I->getFalseValue()); 403a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling e.function = 0; 40439da078977ae98b6bf1c3c76a472ed24f5f2a2d2Bill Wendling e.type = I->getType(); 405a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling e.opcode = Expression::SELECT; 406a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 40785df6b43403d3ebf5d80023a85699c6fb254941aBill Wendling return e; 40885df6b43403d3ebf5d80023a85699c6fb254941aBill Wendling} 40985df6b43403d3ebf5d80023a85699c6fb254941aBill Wendling 41085df6b43403d3ebf5d80023a85699c6fb254941aBill WendlingExpression ValueTable::create_expression(GetElementPtrInst* G) { 411a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling Expression e; 412a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 413a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling e.firstVN = hash_operand(G->getPointerOperand()); 414a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling e.secondVN = 0; 415a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling e.thirdVN = 0; 416a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling e.function = 0; 41739da078977ae98b6bf1c3c76a472ed24f5f2a2d2Bill Wendling e.type = G->getType(); 41839da078977ae98b6bf1c3c76a472ed24f5f2a2d2Bill Wendling e.opcode = Expression::GEP; 41939da078977ae98b6bf1c3c76a472ed24f5f2a2d2Bill Wendling 420ea59f896a672c2e1ef9f02277bce60257aa60989Bill Wendling for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 421ad19d9c4228718b0ac167d0dfa013d14c3c9f135Bill Wendling I != E; ++I) 422ea59f896a672c2e1ef9f02277bce60257aa60989Bill Wendling e.varargs.push_back(hash_operand(*I)); 423a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 424a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return e; 425a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling} 42649f6060f16aec4024d644a6ec4ddd3de9b3e8821Bill Wendling 427e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendling//===----------------------------------------------------------------------===// 428a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling// ValueTable External Functions 429ea59f896a672c2e1ef9f02277bce60257aa60989Bill Wendling//===----------------------------------------------------------------------===// 430ea59f896a672c2e1ef9f02277bce60257aa60989Bill Wendling 431ea59f896a672c2e1ef9f02277bce60257aa60989Bill Wendling/// lookup_or_add - Returns the value number for the specified value, assigning 43285df6b43403d3ebf5d80023a85699c6fb254941aBill Wendling/// it a new number if it did not have one before. 43385df6b43403d3ebf5d80023a85699c6fb254941aBill Wendlinguint32_t ValueTable::lookup_or_add(Value* V) { 43485df6b43403d3ebf5d80023a85699c6fb254941aBill Wendling DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 435a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling if (VI != valueNumbering.end()) 436a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return VI->second; 437a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 438c342d9d345acdbd95577c7c6e9ce7d3a1bdb57bfBill Wendling if (CallInst* C = dyn_cast<CallInst>(V)) { 439c342d9d345acdbd95577c7c6e9ce7d3a1bdb57bfBill Wendling if (AA->onlyReadsMemory(C)) { // includes doesNotAccessMemory 440c342d9d345acdbd95577c7c6e9ce7d3a1bdb57bfBill Wendling Expression e = create_expression(C); 441c342d9d345acdbd95577c7c6e9ce7d3a1bdb57bfBill Wendling 442a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 443a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling if (EI != expressionNumbering.end()) { 444a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling valueNumbering.insert(std::make_pair(V, EI->second)); 445a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return EI->second; 446a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } else { 447e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendling expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 448a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling valueNumbering.insert(std::make_pair(V, nextValueNumber)); 449a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 450a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return nextValueNumber++; 451a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } 452a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } else { 453a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling valueNumbering.insert(std::make_pair(V, nextValueNumber)); 454a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return nextValueNumber++; 455a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } 456a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 457a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling Expression e = create_expression(BO); 458a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 459a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 460a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling if (EI != expressionNumbering.end()) { 461a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling valueNumbering.insert(std::make_pair(V, EI->second)); 462a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return EI->second; 463a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } else { 464a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 465a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling valueNumbering.insert(std::make_pair(V, nextValueNumber)); 46664754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling 467a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return nextValueNumber++; 468a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } 469a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 470c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling Expression e = create_expression(C); 471c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling 472817abdd8b055059e5930a15704b9f52da4236456Bill Wendling DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 473a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling if (EI != expressionNumbering.end()) { 474a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling valueNumbering.insert(std::make_pair(V, EI->second)); 475a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return EI->second; 47687de71cb9f12d874e88d4f314ab245985c1b36bcBill Wendling } else { 47787de71cb9f12d874e88d4f314ab245985c1b36bcBill Wendling expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 47864754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling valueNumbering.insert(std::make_pair(V, nextValueNumber)); 47964754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling 48064754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling return nextValueNumber++; 48164754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling } 48264754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 48364754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling Expression e = create_expression(U); 48464754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling 48564754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 48664754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling if (EI != expressionNumbering.end()) { 48764754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling valueNumbering.insert(std::make_pair(V, EI->second)); 48864754f499058b5dc748ea6d06a084af0ed539ec4Bill Wendling return EI->second; 48987de71cb9f12d874e88d4f314ab245985c1b36bcBill Wendling } else { 49087de71cb9f12d874e88d4f314ab245985c1b36bcBill Wendling expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 491a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling valueNumbering.insert(std::make_pair(V, nextValueNumber)); 492a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 493a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return nextValueNumber++; 494a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } 495a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 496a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling Expression e = create_expression(U); 497a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 498a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 499a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling if (EI != expressionNumbering.end()) { 500a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling valueNumbering.insert(std::make_pair(V, EI->second)); 501a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return EI->second; 502114baee1fa017daefad2339c77b45b9ca3d79a41Bill Wendling } else { 503a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 504a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling valueNumbering.insert(std::make_pair(V, nextValueNumber)); 505a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 506a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return nextValueNumber++; 507a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } 508a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 509a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling Expression e = create_expression(U); 510a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 511a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 512ab39afa9d9b99c61842c8e3d0eb706bd16efdcf3Kostya Serebryany if (EI != expressionNumbering.end()) { 513ab39afa9d9b99c61842c8e3d0eb706bd16efdcf3Kostya Serebryany valueNumbering.insert(std::make_pair(V, EI->second)); 514a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return EI->second; 515a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } else { 516a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 517a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling valueNumbering.insert(std::make_pair(V, nextValueNumber)); 518a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling 519a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return nextValueNumber++; 520a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } 521a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 522c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling Expression e = create_expression(U); 523f9271ea159b97e2febedcf095c3c4122cb24d077Bill Wendling 524c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 525c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling if (EI != expressionNumbering.end()) { 526c22f4aa886443507f8406d30d118fdeeac6a8c6cBill Wendling valueNumbering.insert(std::make_pair(V, EI->second)); 527a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling return EI->second; 528a90a99a82b9c5c39fc6dbee9c266dcd7b107fe2fBill Wendling } else { 5298e47daf2858e980210f3e1f007036b24da342c29Bill Wendling expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 5308e47daf2858e980210f3e1f007036b24da342c29Bill Wendling valueNumbering.insert(std::make_pair(V, nextValueNumber)); 5318e47daf2858e980210f3e1f007036b24da342c29Bill Wendling 532e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendling return nextValueNumber++; 5338e47daf2858e980210f3e1f007036b24da342c29Bill Wendling } 5348e47daf2858e980210f3e1f007036b24da342c29Bill Wendling } else if (CastInst* U = dyn_cast<CastInst>(V)) { 5358e47daf2858e980210f3e1f007036b24da342c29Bill Wendling Expression e = create_expression(U); 53627107f6ab4627fa38bcacad6757ed6d52910f880Bill Wendling 5376091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 5386091ebd172a16a10f1ea66061a5fa7cbf5139e56Reid Spencer if (EI != expressionNumbering.end()) { 539 valueNumbering.insert(std::make_pair(V, EI->second)); 540 return EI->second; 541 } else { 542 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 543 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 544 545 return nextValueNumber++; 546 } 547 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 548 Expression e = create_expression(U); 549 550 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 551 if (EI != expressionNumbering.end()) { 552 valueNumbering.insert(std::make_pair(V, EI->second)); 553 return EI->second; 554 } else { 555 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 556 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 557 558 return nextValueNumber++; 559 } 560 } else { 561 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 562 return nextValueNumber++; 563 } 564} 565 566/// lookup - Returns the value number of the specified value. Fails if 567/// the value has not yet been numbered. 568uint32_t ValueTable::lookup(Value* V) const { 569 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 570 assert(VI != valueNumbering.end() && "Value not numbered?"); 571 return VI->second; 572} 573 574/// clear - Remove all entries from the ValueTable 575void ValueTable::clear() { 576 valueNumbering.clear(); 577 expressionNumbering.clear(); 578 nextValueNumber = 1; 579} 580 581/// erase - Remove a value from the value numbering 582void ValueTable::erase(Value* V) { 583 valueNumbering.erase(V); 584} 585 586//===----------------------------------------------------------------------===// 587// ValueNumberedSet Class 588//===----------------------------------------------------------------------===// 589namespace { 590class VISIBILITY_HIDDEN ValueNumberedSet { 591 private: 592 SmallPtrSet<Value*, 8> contents; 593 BitVector numbers; 594 public: 595 ValueNumberedSet() { numbers.resize(1); } 596 ValueNumberedSet(const ValueNumberedSet& other) { 597 numbers = other.numbers; 598 contents = other.contents; 599 } 600 601 typedef SmallPtrSet<Value*, 8>::iterator iterator; 602 603 iterator begin() { return contents.begin(); } 604 iterator end() { return contents.end(); } 605 606 bool insert(Value* v) { return contents.insert(v); } 607 void insert(iterator I, iterator E) { contents.insert(I, E); } 608 void erase(Value* v) { contents.erase(v); } 609 unsigned count(Value* v) { return contents.count(v); } 610 size_t size() { return contents.size(); } 611 612 void set(unsigned i) { 613 if (i >= numbers.size()) 614 numbers.resize(i+1); 615 616 numbers.set(i); 617 } 618 619 void operator=(const ValueNumberedSet& other) { 620 contents = other.contents; 621 numbers = other.numbers; 622 } 623 624 void reset(unsigned i) { 625 if (i < numbers.size()) 626 numbers.reset(i); 627 } 628 629 bool test(unsigned i) { 630 if (i >= numbers.size()) 631 return false; 632 633 return numbers.test(i); 634 } 635 636 void clear() { 637 contents.clear(); 638 numbers.clear(); 639 } 640}; 641} 642 643//===----------------------------------------------------------------------===// 644// GVN Pass 645//===----------------------------------------------------------------------===// 646 647namespace { 648 649 class VISIBILITY_HIDDEN GVN : public FunctionPass { 650 bool runOnFunction(Function &F); 651 public: 652 static char ID; // Pass identification, replacement for typeid 653 GVN() : FunctionPass((intptr_t)&ID) { } 654 655 private: 656 ValueTable VN; 657 658 DenseMap<BasicBlock*, ValueNumberedSet> availableOut; 659 660 typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType; 661 PhiMapType phiMap; 662 663 664 // This transformation requires dominator postdominator info 665 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 666 AU.setPreservesCFG(); 667 AU.addRequired<DominatorTree>(); 668 AU.addRequired<MemoryDependenceAnalysis>(); 669 AU.addRequired<AliasAnalysis>(); 670 AU.addRequired<TargetData>(); 671 AU.addPreserved<AliasAnalysis>(); 672 AU.addPreserved<MemoryDependenceAnalysis>(); 673 AU.addPreserved<TargetData>(); 674 } 675 676 // Helper fuctions 677 // FIXME: eliminate or document these better 678 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ; 679 void val_insert(ValueNumberedSet& s, Value* v); 680 bool processLoad(LoadInst* L, 681 DenseMap<Value*, LoadInst*> &lastLoad, 682 SmallVectorImpl<Instruction*> &toErase); 683 bool processStore(StoreInst *SI, SmallVectorImpl<Instruction*> &toErase); 684 bool processInstruction(Instruction* I, 685 ValueNumberedSet& currAvail, 686 DenseMap<Value*, LoadInst*>& lastSeenLoad, 687 SmallVectorImpl<Instruction*> &toErase); 688 bool processNonLocalLoad(LoadInst* L, 689 SmallVectorImpl<Instruction*> &toErase); 690 bool processMemCpy(MemCpyInst* M, MemCpyInst* MDep, 691 SmallVectorImpl<Instruction*> &toErase); 692 bool performCallSlotOptzn(MemCpyInst* cpy, CallInst* C, 693 SmallVectorImpl<Instruction*> &toErase); 694 Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, 695 DenseMap<BasicBlock*, Value*> &Phis, 696 bool top_level = false); 697 void dump(DenseMap<BasicBlock*, Value*>& d); 698 bool iterateOnFunction(Function &F); 699 Value* CollapsePhi(PHINode* p); 700 bool isSafeReplacement(PHINode* p, Instruction* inst); 701 }; 702 703 char GVN::ID = 0; 704} 705 706// createGVNPass - The public interface to this file... 707FunctionPass *llvm::createGVNPass() { return new GVN(); } 708 709static RegisterPass<GVN> X("gvn", 710 "Global Value Numbering"); 711 712/// find_leader - Given a set and a value number, return the first 713/// element of the set with that value number, or 0 if no such element 714/// is present 715Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) { 716 if (!vals.test(v)) 717 return 0; 718 719 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end(); 720 I != E; ++I) 721 if (v == VN.lookup(*I)) 722 return *I; 723 724 assert(0 && "No leader found, but present bit is set?"); 725 return 0; 726} 727 728/// val_insert - Insert a value into a set only if there is not a value 729/// with the same value number already in the set 730void GVN::val_insert(ValueNumberedSet& s, Value* v) { 731 uint32_t num = VN.lookup(v); 732 if (!s.test(num)) 733 s.insert(v); 734} 735 736void GVN::dump(DenseMap<BasicBlock*, Value*>& d) { 737 printf("{\n"); 738 for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(), 739 E = d.end(); I != E; ++I) { 740 if (I->second == MemoryDependenceAnalysis::None) 741 printf("None\n"); 742 else 743 I->second->dump(); 744 } 745 printf("}\n"); 746} 747 748Value* GVN::CollapsePhi(PHINode* p) { 749 DominatorTree &DT = getAnalysis<DominatorTree>(); 750 Value* constVal = p->hasConstantValue(); 751 752 if (!constVal) return 0; 753 754 Instruction* inst = dyn_cast<Instruction>(constVal); 755 if (!inst) 756 return constVal; 757 758 if (DT.dominates(inst, p)) 759 if (isSafeReplacement(p, inst)) 760 return inst; 761 return 0; 762} 763 764bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) { 765 if (!isa<PHINode>(inst)) 766 return true; 767 768 for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end(); 769 UI != E; ++UI) 770 if (PHINode* use_phi = dyn_cast<PHINode>(UI)) 771 if (use_phi->getParent() == inst->getParent()) 772 return false; 773 774 return true; 775} 776 777/// GetValueForBlock - Get the value to use within the specified basic block. 778/// available values are in Phis. 779Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, 780 DenseMap<BasicBlock*, Value*> &Phis, 781 bool top_level) { 782 783 // If we have already computed this value, return the previously computed val. 784 DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 785 if (V != Phis.end() && !top_level) return V->second; 786 787 BasicBlock* singlePred = BB->getSinglePredecessor(); 788 if (singlePred) { 789 Value *ret = GetValueForBlock(singlePred, orig, Phis); 790 Phis[BB] = ret; 791 return ret; 792 } 793 794 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 795 // now, then get values to fill in the incoming values for the PHI. 796 PHINode *PN = PHINode::Create(orig->getType(), orig->getName()+".rle", 797 BB->begin()); 798 PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 799 800 if (Phis.count(BB) == 0) 801 Phis.insert(std::make_pair(BB, PN)); 802 803 // Fill in the incoming values for the block. 804 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 805 Value* val = GetValueForBlock(*PI, orig, Phis); 806 PN->addIncoming(val, *PI); 807 } 808 809 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 810 AA.copyValue(orig, PN); 811 812 // Attempt to collapse PHI nodes that are trivially redundant 813 Value* v = CollapsePhi(PN); 814 if (!v) { 815 // Cache our phi construction results 816 phiMap[orig->getPointerOperand()].insert(PN); 817 return PN; 818 } 819 820 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 821 822 MD.removeInstruction(PN); 823 PN->replaceAllUsesWith(v); 824 825 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 826 E = Phis.end(); I != E; ++I) 827 if (I->second == PN) 828 I->second = v; 829 830 PN->eraseFromParent(); 831 832 Phis[BB] = v; 833 return v; 834} 835 836/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are 837/// non-local by performing PHI construction. 838bool GVN::processNonLocalLoad(LoadInst* L, 839 SmallVectorImpl<Instruction*> &toErase) { 840 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 841 842 // Find the non-local dependencies of the load 843 DenseMap<BasicBlock*, Value*> deps; 844 MD.getNonLocalDependency(L, deps); 845 846 DenseMap<BasicBlock*, Value*> repl; 847 848 // Filter out useless results (non-locals, etc) 849 for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end(); 850 I != E; ++I) { 851 if (I->second == MemoryDependenceAnalysis::None) 852 return false; 853 854 if (I->second == MemoryDependenceAnalysis::NonLocal) 855 continue; 856 857 if (StoreInst* S = dyn_cast<StoreInst>(I->second)) { 858 if (S->getPointerOperand() != L->getPointerOperand()) 859 return false; 860 repl[I->first] = S->getOperand(0); 861 } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) { 862 if (LD->getPointerOperand() != L->getPointerOperand()) 863 return false; 864 repl[I->first] = LD; 865 } else { 866 return false; 867 } 868 } 869 870 // Use cached PHI construction information from previous runs 871 SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()]; 872 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 873 I != E; ++I) { 874 if ((*I)->getParent() == L->getParent()) { 875 MD.removeInstruction(L); 876 L->replaceAllUsesWith(*I); 877 toErase.push_back(L); 878 NumGVNLoad++; 879 return true; 880 } 881 882 repl.insert(std::make_pair((*I)->getParent(), *I)); 883 } 884 885 // Perform PHI construction 886 SmallPtrSet<BasicBlock*, 4> visited; 887 Value* v = GetValueForBlock(L->getParent(), L, repl, true); 888 889 MD.removeInstruction(L); 890 L->replaceAllUsesWith(v); 891 toErase.push_back(L); 892 NumGVNLoad++; 893 894 return true; 895} 896 897/// processLoad - Attempt to eliminate a load, first by eliminating it 898/// locally, and then attempting non-local elimination if that fails. 899bool GVN::processLoad(LoadInst *L, DenseMap<Value*, LoadInst*> &lastLoad, 900 SmallVectorImpl<Instruction*> &toErase) { 901 if (L->isVolatile()) { 902 lastLoad[L->getPointerOperand()] = L; 903 return false; 904 } 905 906 Value* pointer = L->getPointerOperand(); 907 LoadInst*& last = lastLoad[pointer]; 908 909 // ... to a pointer that has been loaded from before... 910 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 911 bool removedNonLocal = false; 912 Instruction* dep = MD.getDependency(L); 913 if (dep == MemoryDependenceAnalysis::NonLocal && 914 L->getParent() != &L->getParent()->getParent()->getEntryBlock()) { 915 removedNonLocal = processNonLocalLoad(L, toErase); 916 917 if (!removedNonLocal) 918 last = L; 919 920 return removedNonLocal; 921 } 922 923 924 bool deletedLoad = false; 925 926 // Walk up the dependency chain until we either find 927 // a dependency we can use, or we can't walk any further 928 while (dep != MemoryDependenceAnalysis::None && 929 dep != MemoryDependenceAnalysis::NonLocal && 930 (isa<LoadInst>(dep) || isa<StoreInst>(dep))) { 931 // ... that depends on a store ... 932 if (StoreInst* S = dyn_cast<StoreInst>(dep)) { 933 if (S->getPointerOperand() == pointer) { 934 // Remove it! 935 MD.removeInstruction(L); 936 937 L->replaceAllUsesWith(S->getOperand(0)); 938 toErase.push_back(L); 939 deletedLoad = true; 940 NumGVNLoad++; 941 } 942 943 // Whether we removed it or not, we can't 944 // go any further 945 break; 946 } else if (!last) { 947 // If we don't depend on a store, and we haven't 948 // been loaded before, bail. 949 break; 950 } else if (dep == last) { 951 // Remove it! 952 MD.removeInstruction(L); 953 954 L->replaceAllUsesWith(last); 955 toErase.push_back(L); 956 deletedLoad = true; 957 NumGVNLoad++; 958 959 break; 960 } else { 961 dep = MD.getDependency(L, dep); 962 } 963 } 964 965 if (dep != MemoryDependenceAnalysis::None && 966 dep != MemoryDependenceAnalysis::NonLocal && 967 isa<AllocationInst>(dep)) { 968 // Check that this load is actually from the 969 // allocation we found 970 Value* v = L->getOperand(0); 971 while (true) { 972 if (BitCastInst *BC = dyn_cast<BitCastInst>(v)) 973 v = BC->getOperand(0); 974 else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(v)) 975 v = GEP->getOperand(0); 976 else 977 break; 978 } 979 if (v == dep) { 980 // If this load depends directly on an allocation, there isn't 981 // anything stored there; therefore, we can optimize this load 982 // to undef. 983 MD.removeInstruction(L); 984 985 L->replaceAllUsesWith(UndefValue::get(L->getType())); 986 toErase.push_back(L); 987 deletedLoad = true; 988 NumGVNLoad++; 989 } 990 } 991 992 if (!deletedLoad) 993 last = L; 994 995 return deletedLoad; 996} 997 998/// isBytewiseValue - If the specified value can be set by repeating the same 999/// byte in memory, return the i8 value that it is represented with. This is 1000/// true for all i8 values obviously, but is also true for i32 0, i32 -1, 1001/// i16 0xF0F0, double 0.0 etc. If the value can't be handled with a repeated 1002/// byte store (e.g. i16 0x1234), return null. 1003static Value *isBytewiseValue(Value *V) { 1004 // All byte-wide stores are splatable, even of arbitrary variables. 1005 if (V->getType() == Type::Int8Ty) return V; 1006 1007 // Constant float and double values can be handled as integer values if the 1008 // corresponding integer value is "byteable". An important case is 0.0. 1009 if (ConstantFP *CFP = dyn_cast<ConstantFP>(V)) { 1010 if (CFP->getType() == Type::FloatTy) 1011 V = ConstantExpr::getBitCast(CFP, Type::Int32Ty); 1012 if (CFP->getType() == Type::DoubleTy) 1013 V = ConstantExpr::getBitCast(CFP, Type::Int64Ty); 1014 // Don't handle long double formats, which have strange constraints. 1015 } 1016 1017 // We can handle constant integers that are power of two in size and a 1018 // multiple of 8 bits. 1019 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 1020 unsigned Width = CI->getBitWidth(); 1021 if (isPowerOf2_32(Width) && Width > 8) { 1022 // We can handle this value if the recursive binary decomposition is the 1023 // same at all levels. 1024 APInt Val = CI->getValue(); 1025 APInt Val2; 1026 while (Val.getBitWidth() != 8) { 1027 unsigned NextWidth = Val.getBitWidth()/2; 1028 Val2 = Val.lshr(NextWidth); 1029 Val2.trunc(Val.getBitWidth()/2); 1030 Val.trunc(Val.getBitWidth()/2); 1031 1032 // If the top/bottom halves aren't the same, reject it. 1033 if (Val != Val2) 1034 return 0; 1035 } 1036 return ConstantInt::get(Val); 1037 } 1038 } 1039 1040 // Conceptually, we could handle things like: 1041 // %a = zext i8 %X to i16 1042 // %b = shl i16 %a, 8 1043 // %c = or i16 %a, %b 1044 // but until there is an example that actually needs this, it doesn't seem 1045 // worth worrying about. 1046 return 0; 1047} 1048 1049static int64_t GetOffsetFromIndex(const GetElementPtrInst *GEP, unsigned Idx, 1050 bool &VariableIdxFound, TargetData &TD) { 1051 // Skip over the first indices. 1052 gep_type_iterator GTI = gep_type_begin(GEP); 1053 for (unsigned i = 1; i != Idx; ++i, ++GTI) 1054 /*skip along*/; 1055 1056 // Compute the offset implied by the rest of the indices. 1057 int64_t Offset = 0; 1058 for (unsigned i = Idx, e = GEP->getNumOperands(); i != e; ++i, ++GTI) { 1059 ConstantInt *OpC = dyn_cast<ConstantInt>(GEP->getOperand(i)); 1060 if (OpC == 0) 1061 return VariableIdxFound = true; 1062 if (OpC->isZero()) continue; // No offset. 1063 1064 // Handle struct indices, which add their field offset to the pointer. 1065 if (const StructType *STy = dyn_cast<StructType>(*GTI)) { 1066 Offset += TD.getStructLayout(STy)->getElementOffset(OpC->getZExtValue()); 1067 continue; 1068 } 1069 1070 // Otherwise, we have a sequential type like an array or vector. Multiply 1071 // the index by the ElementSize. 1072 uint64_t Size = TD.getABITypeSize(GTI.getIndexedType()); 1073 Offset += Size*OpC->getSExtValue(); 1074 } 1075 1076 return Offset; 1077} 1078 1079/// IsPointerOffset - Return true if Ptr1 is provably equal to Ptr2 plus a 1080/// constant offset, and return that constant offset. For example, Ptr1 might 1081/// be &A[42], and Ptr2 might be &A[40]. In this case offset would be -8. 1082static bool IsPointerOffset(Value *Ptr1, Value *Ptr2, int64_t &Offset, 1083 TargetData &TD) { 1084 // Right now we handle the case when Ptr1/Ptr2 are both GEPs with an identical 1085 // base. After that base, they may have some number of common (and 1086 // potentially variable) indices. After that they handle some constant 1087 // offset, which determines their offset from each other. At this point, we 1088 // handle no other case. 1089 GetElementPtrInst *GEP1 = dyn_cast<GetElementPtrInst>(Ptr1); 1090 GetElementPtrInst *GEP2 = dyn_cast<GetElementPtrInst>(Ptr2); 1091 if (!GEP1 || !GEP2 || GEP1->getOperand(0) != GEP2->getOperand(0)) 1092 return false; 1093 1094 // Skip any common indices and track the GEP types. 1095 unsigned Idx = 1; 1096 for (; Idx != GEP1->getNumOperands() && Idx != GEP2->getNumOperands(); ++Idx) 1097 if (GEP1->getOperand(Idx) != GEP2->getOperand(Idx)) 1098 break; 1099 1100 bool VariableIdxFound = false; 1101 int64_t Offset1 = GetOffsetFromIndex(GEP1, Idx, VariableIdxFound, TD); 1102 int64_t Offset2 = GetOffsetFromIndex(GEP2, Idx, VariableIdxFound, TD); 1103 if (VariableIdxFound) return false; 1104 1105 Offset = Offset2-Offset1; 1106 return true; 1107} 1108 1109 1110/// MemsetRange - Represents a range of memset'd bytes with the ByteVal value. 1111/// This allows us to analyze stores like: 1112/// store 0 -> P+1 1113/// store 0 -> P+0 1114/// store 0 -> P+3 1115/// store 0 -> P+2 1116/// which sometimes happens with stores to arrays of structs etc. When we see 1117/// the first store, we make a range [1, 2). The second store extends the range 1118/// to [0, 2). The third makes a new range [2, 3). The fourth store joins the 1119/// two ranges into [0, 3) which is memset'able. 1120namespace { 1121struct MemsetRange { 1122 // Start/End - A semi range that describes the span that this range covers. 1123 // The range is closed at the start and open at the end: [Start, End). 1124 int64_t Start, End; 1125 1126 /// StartPtr - The getelementptr instruction that points to the start of the 1127 /// range. 1128 Value *StartPtr; 1129 1130 /// Alignment - The known alignment of the first store. 1131 unsigned Alignment; 1132 1133 /// TheStores - The actual stores that make up this range. 1134 SmallVector<StoreInst*, 16> TheStores; 1135 1136 bool isProfitableToUseMemset(const TargetData &TD) const; 1137 1138}; 1139} // end anon namespace 1140 1141bool MemsetRange::isProfitableToUseMemset(const TargetData &TD) const { 1142 // If we found more than 8 stores to merge or 64 bytes, use memset. 1143 if (TheStores.size() >= 8 || End-Start >= 64) return true; 1144 1145 // Assume that the code generator is capable of merging pairs of stores 1146 // together if it wants to. 1147 if (TheStores.size() <= 2) return false; 1148 1149 // If we have fewer than 8 stores, it can still be worthwhile to do this. 1150 // For example, merging 4 i8 stores into an i32 store is useful almost always. 1151 // However, merging 2 32-bit stores isn't useful on a 32-bit architecture (the 1152 // memset will be split into 2 32-bit stores anyway) and doing so can 1153 // pessimize the llvm optimizer. 1154 // 1155 // Since we don't have perfect knowledge here, make some assumptions: assume 1156 // the maximum GPR width is the same size as the pointer size and assume that 1157 // this width can be stored. If so, check to see whether we will end up 1158 // actually reducing the number of stores used. 1159 unsigned Bytes = unsigned(End-Start); 1160 unsigned NumPointerStores = Bytes/TD.getPointerSize(); 1161 1162 // Assume the remaining bytes if any are done a byte at a time. 1163 unsigned NumByteStores = Bytes - NumPointerStores*TD.getPointerSize(); 1164 1165 // If we will reduce the # stores (according to this heuristic), do the 1166 // transformation. This encourages merging 4 x i8 -> i32 and 2 x i16 -> i32 1167 // etc. 1168 return TheStores.size() > NumPointerStores+NumByteStores; 1169} 1170 1171 1172namespace { 1173class MemsetRanges { 1174 /// Ranges - A sorted list of the memset ranges. We use std::list here 1175 /// because each element is relatively large and expensive to copy. 1176 std::list<MemsetRange> Ranges; 1177 typedef std::list<MemsetRange>::iterator range_iterator; 1178 TargetData &TD; 1179public: 1180 MemsetRanges(TargetData &td) : TD(td) {} 1181 1182 typedef std::list<MemsetRange>::const_iterator const_iterator; 1183 const_iterator begin() const { return Ranges.begin(); } 1184 const_iterator end() const { return Ranges.end(); } 1185 bool empty() const { return Ranges.empty(); } 1186 1187 void addStore(int64_t OffsetFromFirst, StoreInst *SI); 1188}; 1189 1190} // end anon namespace 1191 1192 1193/// addStore - Add a new store to the MemsetRanges data structure. This adds a 1194/// new range for the specified store at the specified offset, merging into 1195/// existing ranges as appropriate. 1196void MemsetRanges::addStore(int64_t Start, StoreInst *SI) { 1197 int64_t End = Start+TD.getTypeStoreSize(SI->getOperand(0)->getType()); 1198 1199 // Do a linear search of the ranges to see if this can be joined and/or to 1200 // find the insertion point in the list. We keep the ranges sorted for 1201 // simplicity here. This is a linear search of a linked list, which is ugly, 1202 // however the number of ranges is limited, so this won't get crazy slow. 1203 range_iterator I = Ranges.begin(), E = Ranges.end(); 1204 1205 while (I != E && Start > I->End) 1206 ++I; 1207 1208 // We now know that I == E, in which case we didn't find anything to merge 1209 // with, or that Start <= I->End. If End < I->Start or I == E, then we need 1210 // to insert a new range. Handle this now. 1211 if (I == E || End < I->Start) { 1212 MemsetRange &R = *Ranges.insert(I, MemsetRange()); 1213 R.Start = Start; 1214 R.End = End; 1215 R.StartPtr = SI->getPointerOperand(); 1216 R.Alignment = SI->getAlignment(); 1217 R.TheStores.push_back(SI); 1218 return; 1219 } 1220 1221 // This store overlaps with I, add it. 1222 I->TheStores.push_back(SI); 1223 1224 // At this point, we may have an interval that completely contains our store. 1225 // If so, just add it to the interval and return. 1226 if (I->Start <= Start && I->End >= End) 1227 return; 1228 1229 // Now we know that Start <= I->End and End >= I->Start so the range overlaps 1230 // but is not entirely contained within the range. 1231 1232 // See if the range extends the start of the range. In this case, it couldn't 1233 // possibly cause it to join the prior range, because otherwise we would have 1234 // stopped on *it*. 1235 if (Start < I->Start) { 1236 I->Start = Start; 1237 I->StartPtr = SI->getPointerOperand(); 1238 } 1239 1240 // Now we know that Start <= I->End and Start >= I->Start (so the startpoint 1241 // is in or right at the end of I), and that End >= I->Start. Extend I out to 1242 // End. 1243 if (End > I->End) { 1244 I->End = End; 1245 range_iterator NextI = I;; 1246 while (++NextI != E && End >= NextI->Start) { 1247 // Merge the range in. 1248 I->TheStores.append(NextI->TheStores.begin(), NextI->TheStores.end()); 1249 if (NextI->End > I->End) 1250 I->End = NextI->End; 1251 Ranges.erase(NextI); 1252 NextI = I; 1253 } 1254 } 1255} 1256 1257 1258 1259/// processStore - When GVN is scanning forward over instructions, we look for 1260/// some other patterns to fold away. In particular, this looks for stores to 1261/// neighboring locations of memory. If it sees enough consequtive ones 1262/// (currently 4) it attempts to merge them together into a memcpy/memset. 1263bool GVN::processStore(StoreInst *SI, SmallVectorImpl<Instruction*> &toErase) { 1264 if (!FormMemSet) return false; 1265 if (SI->isVolatile()) return false; 1266 1267 // There are two cases that are interesting for this code to handle: memcpy 1268 // and memset. Right now we only handle memset. 1269 1270 // Ensure that the value being stored is something that can be memset'able a 1271 // byte at a time like "0" or "-1" or any width, as well as things like 1272 // 0xA0A0A0A0 and 0.0. 1273 Value *ByteVal = isBytewiseValue(SI->getOperand(0)); 1274 if (!ByteVal) 1275 return false; 1276 1277 TargetData &TD = getAnalysis<TargetData>(); 1278 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 1279 1280 // Okay, so we now have a single store that can be splatable. Scan to find 1281 // all subsequent stores of the same value to offset from the same pointer. 1282 // Join these together into ranges, so we can decide whether contiguous blocks 1283 // are stored. 1284 MemsetRanges Ranges(TD); 1285 1286 Value *StartPtr = SI->getPointerOperand(); 1287 1288 BasicBlock::iterator BI = SI; 1289 for (++BI; !isa<TerminatorInst>(BI); ++BI) { 1290 if (isa<CallInst>(BI) || isa<InvokeInst>(BI)) { 1291 // If the call is readnone, ignore it, otherwise bail out. We don't even 1292 // allow readonly here because we don't want something like: 1293 // A[1] = 2; strlen(A); A[2] = 2; -> memcpy(A, ...); strlen(A). 1294 if (AA.getModRefBehavior(CallSite::get(BI)) == 1295 AliasAnalysis::DoesNotAccessMemory) 1296 continue; 1297 1298 // TODO: If this is a memset, try to join it in. 1299 1300 break; 1301 } else if (isa<VAArgInst>(BI) || isa<LoadInst>(BI)) 1302 break; 1303 1304 // If this is a non-store instruction it is fine, ignore it. 1305 StoreInst *NextStore = dyn_cast<StoreInst>(BI); 1306 if (NextStore == 0) continue; 1307 1308 // If this is a store, see if we can merge it in. 1309 if (NextStore->isVolatile()) break; 1310 1311 // Check to see if this stored value is of the same byte-splattable value. 1312 if (ByteVal != isBytewiseValue(NextStore->getOperand(0))) 1313 break; 1314 1315 // Check to see if this store is to a constant offset from the start ptr. 1316 int64_t Offset; 1317 if (!IsPointerOffset(StartPtr, NextStore->getPointerOperand(), Offset, TD)) 1318 break; 1319 1320 Ranges.addStore(Offset, NextStore); 1321 } 1322 1323 // If we have no ranges, then we just had a single store with nothing that 1324 // could be merged in. This is a very common case of course. 1325 if (Ranges.empty()) 1326 return false; 1327 1328 // If we had at least one store that could be merged in, add the starting 1329 // store as well. We try to avoid this unless there is at least something 1330 // interesting as a small compile-time optimization. 1331 Ranges.addStore(0, SI); 1332 1333 1334 Function *MemSetF = 0; 1335 1336 // Now that we have full information about ranges, loop over the ranges and 1337 // emit memset's for anything big enough to be worthwhile. 1338 bool MadeChange = false; 1339 for (MemsetRanges::const_iterator I = Ranges.begin(), E = Ranges.end(); 1340 I != E; ++I) { 1341 const MemsetRange &Range = *I; 1342 1343 if (Range.TheStores.size() == 1) continue; 1344 1345 // If it is profitable to lower this range to memset, do so now. 1346 if (!Range.isProfitableToUseMemset(TD)) 1347 continue; 1348 1349 // Otherwise, we do want to transform this! Create a new memset. We put 1350 // the memset right before the first instruction that isn't part of this 1351 // memset block. This ensure that the memset is dominated by any addressing 1352 // instruction needed by the start of the block. 1353 BasicBlock::iterator InsertPt = BI; 1354 1355 if (MemSetF == 0) 1356 MemSetF = Intrinsic::getDeclaration(SI->getParent()->getParent() 1357 ->getParent(), Intrinsic::memset_i64); 1358 1359 // Get the starting pointer of the block. 1360 StartPtr = Range.StartPtr; 1361 1362 // Cast the start ptr to be i8* as memset requires. 1363 const Type *i8Ptr = PointerType::getUnqual(Type::Int8Ty); 1364 if (StartPtr->getType() != i8Ptr) 1365 StartPtr = new BitCastInst(StartPtr, i8Ptr, StartPtr->getNameStart(), 1366 InsertPt); 1367 1368 Value *Ops[] = { 1369 StartPtr, ByteVal, // Start, value 1370 ConstantInt::get(Type::Int64Ty, Range.End-Range.Start), // size 1371 ConstantInt::get(Type::Int32Ty, Range.Alignment) // align 1372 }; 1373 Value *C = CallInst::Create(MemSetF, Ops, Ops+4, "", InsertPt); 1374 DEBUG(cerr << "Replace stores:\n"; 1375 for (unsigned i = 0, e = Range.TheStores.size(); i != e; ++i) 1376 cerr << *Range.TheStores[i]; 1377 cerr << "With: " << *C); C=C; 1378 1379 // Zap all the stores. 1380 toErase.append(Range.TheStores.begin(), Range.TheStores.end()); 1381 ++NumMemSetInfer; 1382 MadeChange = true; 1383 } 1384 1385 return MadeChange; 1386} 1387 1388 1389/// performCallSlotOptzn - takes a memcpy and a call that it depends on, 1390/// and checks for the possibility of a call slot optimization by having 1391/// the call write its result directly into the destination of the memcpy. 1392bool GVN::performCallSlotOptzn(MemCpyInst *cpy, CallInst *C, 1393 SmallVectorImpl<Instruction*> &toErase) { 1394 // The general transformation to keep in mind is 1395 // 1396 // call @func(..., src, ...) 1397 // memcpy(dest, src, ...) 1398 // 1399 // -> 1400 // 1401 // memcpy(dest, src, ...) 1402 // call @func(..., dest, ...) 1403 // 1404 // Since moving the memcpy is technically awkward, we additionally check that 1405 // src only holds uninitialized values at the moment of the call, meaning that 1406 // the memcpy can be discarded rather than moved. 1407 1408 // Deliberately get the source and destination with bitcasts stripped away, 1409 // because we'll need to do type comparisons based on the underlying type. 1410 Value* cpyDest = cpy->getDest(); 1411 Value* cpySrc = cpy->getSource(); 1412 CallSite CS = CallSite::get(C); 1413 1414 // We need to be able to reason about the size of the memcpy, so we require 1415 // that it be a constant. 1416 ConstantInt* cpyLength = dyn_cast<ConstantInt>(cpy->getLength()); 1417 if (!cpyLength) 1418 return false; 1419 1420 // Require that src be an alloca. This simplifies the reasoning considerably. 1421 AllocaInst* srcAlloca = dyn_cast<AllocaInst>(cpySrc); 1422 if (!srcAlloca) 1423 return false; 1424 1425 // Check that all of src is copied to dest. 1426 TargetData& TD = getAnalysis<TargetData>(); 1427 1428 ConstantInt* srcArraySize = dyn_cast<ConstantInt>(srcAlloca->getArraySize()); 1429 if (!srcArraySize) 1430 return false; 1431 1432 uint64_t srcSize = TD.getABITypeSize(srcAlloca->getAllocatedType()) * 1433 srcArraySize->getZExtValue(); 1434 1435 if (cpyLength->getZExtValue() < srcSize) 1436 return false; 1437 1438 // Check that accessing the first srcSize bytes of dest will not cause a 1439 // trap. Otherwise the transform is invalid since it might cause a trap 1440 // to occur earlier than it otherwise would. 1441 if (AllocaInst* A = dyn_cast<AllocaInst>(cpyDest)) { 1442 // The destination is an alloca. Check it is larger than srcSize. 1443 ConstantInt* destArraySize = dyn_cast<ConstantInt>(A->getArraySize()); 1444 if (!destArraySize) 1445 return false; 1446 1447 uint64_t destSize = TD.getABITypeSize(A->getAllocatedType()) * 1448 destArraySize->getZExtValue(); 1449 1450 if (destSize < srcSize) 1451 return false; 1452 } else if (Argument* A = dyn_cast<Argument>(cpyDest)) { 1453 // If the destination is an sret parameter then only accesses that are 1454 // outside of the returned struct type can trap. 1455 if (!A->hasStructRetAttr()) 1456 return false; 1457 1458 const Type* StructTy = cast<PointerType>(A->getType())->getElementType(); 1459 uint64_t destSize = TD.getABITypeSize(StructTy); 1460 1461 if (destSize < srcSize) 1462 return false; 1463 } else { 1464 return false; 1465 } 1466 1467 // Check that src is not accessed except via the call and the memcpy. This 1468 // guarantees that it holds only undefined values when passed in (so the final 1469 // memcpy can be dropped), that it is not read or written between the call and 1470 // the memcpy, and that writing beyond the end of it is undefined. 1471 SmallVector<User*, 8> srcUseList(srcAlloca->use_begin(), 1472 srcAlloca->use_end()); 1473 while (!srcUseList.empty()) { 1474 User* UI = srcUseList.back(); 1475 srcUseList.pop_back(); 1476 1477 if (isa<GetElementPtrInst>(UI) || isa<BitCastInst>(UI)) { 1478 for (User::use_iterator I = UI->use_begin(), E = UI->use_end(); 1479 I != E; ++I) 1480 srcUseList.push_back(*I); 1481 } else if (UI != C && UI != cpy) { 1482 return false; 1483 } 1484 } 1485 1486 // Since we're changing the parameter to the callsite, we need to make sure 1487 // that what would be the new parameter dominates the callsite. 1488 DominatorTree& DT = getAnalysis<DominatorTree>(); 1489 if (Instruction* cpyDestInst = dyn_cast<Instruction>(cpyDest)) 1490 if (!DT.dominates(cpyDestInst, C)) 1491 return false; 1492 1493 // In addition to knowing that the call does not access src in some 1494 // unexpected manner, for example via a global, which we deduce from 1495 // the use analysis, we also need to know that it does not sneakily 1496 // access dest. We rely on AA to figure this out for us. 1497 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 1498 if (AA.getModRefInfo(C, cpy->getRawDest(), srcSize) != 1499 AliasAnalysis::NoModRef) 1500 return false; 1501 1502 // All the checks have passed, so do the transformation. 1503 for (unsigned i = 0; i < CS.arg_size(); ++i) 1504 if (CS.getArgument(i) == cpySrc) { 1505 if (cpySrc->getType() != cpyDest->getType()) 1506 cpyDest = CastInst::createPointerCast(cpyDest, cpySrc->getType(), 1507 cpyDest->getName(), C); 1508 CS.setArgument(i, cpyDest); 1509 } 1510 1511 // Drop any cached information about the call, because we may have changed 1512 // its dependence information by changing its parameter. 1513 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1514 MD.dropInstruction(C); 1515 1516 // Remove the memcpy 1517 MD.removeInstruction(cpy); 1518 toErase.push_back(cpy); 1519 1520 return true; 1521} 1522 1523/// processMemCpy - perform simplication of memcpy's. If we have memcpy A which 1524/// copies X to Y, and memcpy B which copies Y to Z, then we can rewrite B to be 1525/// a memcpy from X to Z (or potentially a memmove, depending on circumstances). 1526/// This allows later passes to remove the first memcpy altogether. 1527bool GVN::processMemCpy(MemCpyInst* M, MemCpyInst* MDep, 1528 SmallVectorImpl<Instruction*> &toErase) { 1529 // We can only transforms memcpy's where the dest of one is the source of the 1530 // other 1531 if (M->getSource() != MDep->getDest()) 1532 return false; 1533 1534 // Second, the length of the memcpy's must be the same, or the preceeding one 1535 // must be larger than the following one. 1536 ConstantInt* C1 = dyn_cast<ConstantInt>(MDep->getLength()); 1537 ConstantInt* C2 = dyn_cast<ConstantInt>(M->getLength()); 1538 if (!C1 || !C2) 1539 return false; 1540 1541 uint64_t DepSize = C1->getValue().getZExtValue(); 1542 uint64_t CpySize = C2->getValue().getZExtValue(); 1543 1544 if (DepSize < CpySize) 1545 return false; 1546 1547 // Finally, we have to make sure that the dest of the second does not 1548 // alias the source of the first 1549 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 1550 if (AA.alias(M->getRawDest(), CpySize, MDep->getRawSource(), DepSize) != 1551 AliasAnalysis::NoAlias) 1552 return false; 1553 else if (AA.alias(M->getRawDest(), CpySize, M->getRawSource(), CpySize) != 1554 AliasAnalysis::NoAlias) 1555 return false; 1556 else if (AA.alias(MDep->getRawDest(), DepSize, MDep->getRawSource(), DepSize) 1557 != AliasAnalysis::NoAlias) 1558 return false; 1559 1560 // If all checks passed, then we can transform these memcpy's 1561 Function* MemCpyFun = Intrinsic::getDeclaration( 1562 M->getParent()->getParent()->getParent(), 1563 M->getIntrinsicID()); 1564 1565 std::vector<Value*> args; 1566 args.push_back(M->getRawDest()); 1567 args.push_back(MDep->getRawSource()); 1568 args.push_back(M->getLength()); 1569 args.push_back(M->getAlignment()); 1570 1571 CallInst* C = CallInst::Create(MemCpyFun, args.begin(), args.end(), "", M); 1572 1573 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1574 if (MD.getDependency(C) == MDep) { 1575 MD.dropInstruction(M); 1576 toErase.push_back(M); 1577 return true; 1578 } 1579 1580 MD.removeInstruction(C); 1581 toErase.push_back(C); 1582 return false; 1583} 1584 1585/// processInstruction - When calculating availability, handle an instruction 1586/// by inserting it into the appropriate sets 1587bool GVN::processInstruction(Instruction *I, ValueNumberedSet &currAvail, 1588 DenseMap<Value*, LoadInst*> &lastSeenLoad, 1589 SmallVectorImpl<Instruction*> &toErase) { 1590 if (LoadInst* L = dyn_cast<LoadInst>(I)) 1591 return processLoad(L, lastSeenLoad, toErase); 1592 1593 if (StoreInst *SI = dyn_cast<StoreInst>(I)) 1594 return processStore(SI, toErase); 1595 1596 // Allocations are always uniquely numbered, so we can save time and memory 1597 // by fast failing them. 1598 if (isa<AllocationInst>(I)) 1599 return false; 1600 1601 if (MemCpyInst* M = dyn_cast<MemCpyInst>(I)) { 1602 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1603 1604 // The are two possible optimizations we can do for memcpy: 1605 // a) memcpy-memcpy xform which exposes redundance for DSE 1606 // b) call-memcpy xform for return slot optimization 1607 Instruction* dep = MD.getDependency(M); 1608 if (dep == MemoryDependenceAnalysis::None || 1609 dep == MemoryDependenceAnalysis::NonLocal) 1610 return false; 1611 if (MemCpyInst *MemCpy = dyn_cast<MemCpyInst>(dep)) 1612 return processMemCpy(M, MemCpy, toErase); 1613 if (CallInst* C = dyn_cast<CallInst>(dep)) 1614 return performCallSlotOptzn(M, C, toErase); 1615 return false; 1616 } 1617 1618 unsigned num = VN.lookup_or_add(I); 1619 1620 // Collapse PHI nodes 1621 if (PHINode* p = dyn_cast<PHINode>(I)) { 1622 Value* constVal = CollapsePhi(p); 1623 1624 if (constVal) { 1625 for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end(); 1626 PI != PE; ++PI) 1627 if (PI->second.count(p)) 1628 PI->second.erase(p); 1629 1630 p->replaceAllUsesWith(constVal); 1631 toErase.push_back(p); 1632 } 1633 // Perform value-number based elimination 1634 } else if (currAvail.test(num)) { 1635 Value* repl = find_leader(currAvail, num); 1636 1637 if (CallInst* CI = dyn_cast<CallInst>(I)) { 1638 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 1639 if (!AA.doesNotAccessMemory(CI)) { 1640 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1641 if (cast<Instruction>(repl)->getParent() != CI->getParent() || 1642 MD.getDependency(CI) != MD.getDependency(cast<CallInst>(repl))) { 1643 // There must be an intervening may-alias store, so nothing from 1644 // this point on will be able to be replaced with the preceding call 1645 currAvail.erase(repl); 1646 currAvail.insert(I); 1647 1648 return false; 1649 } 1650 } 1651 } 1652 1653 // Remove it! 1654 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1655 MD.removeInstruction(I); 1656 1657 VN.erase(I); 1658 I->replaceAllUsesWith(repl); 1659 toErase.push_back(I); 1660 return true; 1661 } else if (!I->isTerminator()) { 1662 currAvail.set(num); 1663 currAvail.insert(I); 1664 } 1665 1666 return false; 1667} 1668 1669// GVN::runOnFunction - This is the main transformation entry point for a 1670// function. 1671// 1672bool GVN::runOnFunction(Function& F) { 1673 VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>()); 1674 1675 bool changed = false; 1676 bool shouldContinue = true; 1677 1678 while (shouldContinue) { 1679 shouldContinue = iterateOnFunction(F); 1680 changed |= shouldContinue; 1681 } 1682 1683 return changed; 1684} 1685 1686 1687// GVN::iterateOnFunction - Executes one iteration of GVN 1688bool GVN::iterateOnFunction(Function &F) { 1689 // Clean out global sets from any previous functions 1690 VN.clear(); 1691 availableOut.clear(); 1692 phiMap.clear(); 1693 1694 bool changed_function = false; 1695 1696 DominatorTree &DT = getAnalysis<DominatorTree>(); 1697 1698 SmallVector<Instruction*, 8> toErase; 1699 DenseMap<Value*, LoadInst*> lastSeenLoad; 1700 DenseMap<DomTreeNode*, size_t> numChildrenVisited; 1701 1702 // Top-down walk of the dominator tree 1703 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 1704 E = df_end(DT.getRootNode()); DI != E; ++DI) { 1705 1706 // Get the set to update for this block 1707 ValueNumberedSet& currAvail = availableOut[DI->getBlock()]; 1708 lastSeenLoad.clear(); 1709 1710 BasicBlock* BB = DI->getBlock(); 1711 1712 // A block inherits AVAIL_OUT from its dominator 1713 if (DI->getIDom() != 0) { 1714 currAvail = availableOut[DI->getIDom()->getBlock()]; 1715 1716 numChildrenVisited[DI->getIDom()]++; 1717 1718 if (numChildrenVisited[DI->getIDom()] == DI->getIDom()->getNumChildren()) { 1719 availableOut.erase(DI->getIDom()->getBlock()); 1720 numChildrenVisited.erase(DI->getIDom()); 1721 } 1722 } 1723 1724 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1725 BI != BE;) { 1726 changed_function |= processInstruction(BI, currAvail, 1727 lastSeenLoad, toErase); 1728 if (toErase.empty()) { 1729 ++BI; 1730 continue; 1731 } 1732 1733 // If we need some instructions deleted, do it now. 1734 NumGVNInstr += toErase.size(); 1735 1736 // Avoid iterator invalidation. 1737 bool AtStart = BI == BB->begin(); 1738 if (!AtStart) 1739 --BI; 1740 1741 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 1742 E = toErase.end(); I != E; ++I) 1743 (*I)->eraseFromParent(); 1744 1745 if (AtStart) 1746 BI = BB->begin(); 1747 else 1748 ++BI; 1749 1750 toErase.clear(); 1751 } 1752 } 1753 1754 return changed_function; 1755} 1756