GVN.cpp revision 09713794c17061ae36cc696cfc928c5a0c2bdc75
1f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff//===- GVN.cpp - Eliminate redundant values and loads ------------===// 2f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff// 3f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff// The LLVM Compiler Infrastructure 4f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff// 5f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff// This file is distributed under the University of Illinois Open Source 6f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff// License. See LICENSE.TXT for details. 7f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff// 8f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff//===----------------------------------------------------------------------===// 9f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff// 10f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff// This pass performs global value numbering to eliminate fully redundant 11f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff// instructions. It also performs simple dead load elimination. 12f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff// 13f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff// Note that this pass does the value numbering itself, it does not use the 14f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff// ValueNumbering analysis passes. 15f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff// 16f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff//===----------------------------------------------------------------------===// 17f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff 18f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff#define DEBUG_TYPE "gvn" 19a2496de37abda981ba80d74f529943374c9d6e3dChristopher Tate#include "llvm/Transforms/Scalar.h" 204414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey#include "llvm/BasicBlock.h" 214414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey#include "llvm/Constants.h" 22eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey#include "llvm/DerivedTypes.h" 234414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey#include "llvm/Function.h" 24eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey#include "llvm/Instructions.h" 25eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey#include "llvm/Value.h" 26eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey#include "llvm/ADT/DenseMap.h" 278568db534118fc14cc28100306d51626464ff319Jesse Wilson#include "llvm/ADT/DepthFirstIterator.h" 28f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff#include "llvm/ADT/SmallPtrSet.h" 298568db534118fc14cc28100306d51626464ff319Jesse Wilson#include "llvm/ADT/SmallVector.h" 30a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey#include "llvm/ADT/Statistic.h" 3143be174888684ef3404a43d8434015193c656cceJeff Sharkey#include "llvm/Analysis/Dominators.h" 3243be174888684ef3404a43d8434015193c656cceJeff Sharkey#include "llvm/Analysis/AliasAnalysis.h" 33f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff#include "llvm/Analysis/MemoryDependenceAnalysis.h" 34f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff#include "llvm/Support/CFG.h" 352b4abcd0c7c4361af8ab6d5d7b073fb75ac6d219Dan Egnor#include "llvm/Support/CommandLine.h" 362b4abcd0c7c4361af8ab6d5d7b073fb75ac6d219Dan Egnor#include "llvm/Support/Compiler.h" 372b4abcd0c7c4361af8ab6d5d7b073fb75ac6d219Dan Egnor#include "llvm/Support/Debug.h" 38f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff#include "llvm/Transforms/Utils/BasicBlockUtils.h" 392b4abcd0c7c4361af8ab6d5d7b073fb75ac6d219Dan Egnor#include <cstdio> 402b4abcd0c7c4361af8ab6d5d7b073fb75ac6d219Dan Egnorusing namespace llvm; 41f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff 42f7d0b01387c10f93bf17981d45087810c80f0902Ken ShirriffSTATISTIC(NumGVNInstr, "Number of instructions deleted"); 43f7d0b01387c10f93bf17981d45087810c80f0902Ken ShirriffSTATISTIC(NumGVNLoad, "Number of loads deleted"); 44f7d0b01387c10f93bf17981d45087810c80f0902Ken ShirriffSTATISTIC(NumGVNPRE, "Number of instructions PRE'd"); 45f7d0b01387c10f93bf17981d45087810c80f0902Ken ShirriffSTATISTIC(NumGVNBlocks, "Number of blocks merged"); 46f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff 47f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriffstatic cl::opt<bool> EnablePRE("enable-pre", 48241dde2306202e7655fdf41d5381f2874e47e108Jeff Sharkey cl::init(true), cl::Hidden); 49241dde2306202e7655fdf41d5381f2874e47e108Jeff Sharkey 50241dde2306202e7655fdf41d5381f2874e47e108Jeff Sharkey//===----------------------------------------------------------------------===// 51241dde2306202e7655fdf41d5381f2874e47e108Jeff Sharkey// ValueTable Class 52241dde2306202e7655fdf41d5381f2874e47e108Jeff Sharkey//===----------------------------------------------------------------------===// 53241dde2306202e7655fdf41d5381f2874e47e108Jeff Sharkey 54241dde2306202e7655fdf41d5381f2874e47e108Jeff Sharkey/// This class holds the mapping between values and value numbers. It is used 55d2a458750e5a3d490af09cecb5c28370baf0a913Jeff Sharkey/// as an efficient mechanism to determine the expression-wise equivalence of 56b09540f33a6cabe50edec0ef32d0b1d0b0d96fffJeff Sharkey/// two values. 57b09540f33a6cabe50edec0ef32d0b1d0b0d96fffJeff Sharkeynamespace { 58b09540f33a6cabe50edec0ef32d0b1d0b0d96fffJeff Sharkey struct VISIBILITY_HIDDEN Expression { 59b09540f33a6cabe50edec0ef32d0b1d0b0d96fffJeff Sharkey enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 60b09540f33a6cabe50edec0ef32d0b1d0b0d96fffJeff Sharkey FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 61b09540f33a6cabe50edec0ef32d0b1d0b0d96fffJeff Sharkey ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 62b09540f33a6cabe50edec0ef32d0b1d0b0d96fffJeff Sharkey ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 63b09540f33a6cabe50edec0ef32d0b1d0b0d96fffJeff Sharkey FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 64cdd02c5d76d3dd4e21b5bb922d7fcfb86efec85fJeff Sharkey FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 65cdd02c5d76d3dd4e21b5bb922d7fcfb86efec85fJeff Sharkey FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 66cdd02c5d76d3dd4e21b5bb922d7fcfb86efec85fJeff Sharkey SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 67cdd02c5d76d3dd4e21b5bb922d7fcfb86efec85fJeff Sharkey FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 68cdd02c5d76d3dd4e21b5bb922d7fcfb86efec85fJeff Sharkey PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, CONSTANT, 69cdd02c5d76d3dd4e21b5bb922d7fcfb86efec85fJeff Sharkey EMPTY, TOMBSTONE }; 70cdd02c5d76d3dd4e21b5bb922d7fcfb86efec85fJeff Sharkey 71cdd02c5d76d3dd4e21b5bb922d7fcfb86efec85fJeff Sharkey ExpressionOpcode opcode; 724414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey const Type* type; 734414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey uint32_t firstVN; 744414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey uint32_t secondVN; 754414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey uint32_t thirdVN; 76cdd02c5d76d3dd4e21b5bb922d7fcfb86efec85fJeff Sharkey SmallVector<uint32_t, 4> varargs; 774414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey Value* function; 784414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey 794414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey Expression() { } 804414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey Expression(ExpressionOpcode o) : opcode(o) { } 814414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey 824414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey bool operator==(const Expression &other) const { 83cdd02c5d76d3dd4e21b5bb922d7fcfb86efec85fJeff Sharkey if (opcode != other.opcode) 844414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey return false; 854414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey else if (opcode == EMPTY || opcode == TOMBSTONE) 864414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey return true; 874414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey else if (type != other.type) 884414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey return false; 894414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey else if (function != other.function) 90cdd02c5d76d3dd4e21b5bb922d7fcfb86efec85fJeff Sharkey return false; 914414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey else if (firstVN != other.firstVN) 92234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey return false; 93234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey else if (secondVN != other.secondVN) 94234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey return false; 95234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey else if (thirdVN != other.thirdVN) 96234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey return false; 97234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey else { 98234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey if (varargs.size() != other.varargs.size()) 99234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey return false; 100234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 101234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey for (size_t i = 0; i < varargs.size(); ++i) 1024414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey if (varargs[i] != other.varargs[i]) 103eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey return false; 104eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey 105eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey return true; 106eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey } 107eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey } 108eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey 109eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey bool operator!=(const Expression &other) const { 110eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey if (opcode != other.opcode) 111eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey return true; 112eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey else if (opcode == EMPTY || opcode == TOMBSTONE) 113eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey return false; 11443be174888684ef3404a43d8434015193c656cceJeff Sharkey else if (type != other.type) 11543be174888684ef3404a43d8434015193c656cceJeff Sharkey return true; 11643be174888684ef3404a43d8434015193c656cceJeff Sharkey else if (function != other.function) 11743be174888684ef3404a43d8434015193c656cceJeff Sharkey return true; 11843be174888684ef3404a43d8434015193c656cceJeff Sharkey else if (firstVN != other.firstVN) 119cdd02c5d76d3dd4e21b5bb922d7fcfb86efec85fJeff Sharkey return true; 120cdd02c5d76d3dd4e21b5bb922d7fcfb86efec85fJeff Sharkey else if (secondVN != other.secondVN) 121cdd02c5d76d3dd4e21b5bb922d7fcfb86efec85fJeff Sharkey return true; 122cdd02c5d76d3dd4e21b5bb922d7fcfb86efec85fJeff Sharkey else if (thirdVN != other.thirdVN) 123dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey return true; 124dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey else { 12543be174888684ef3404a43d8434015193c656cceJeff Sharkey if (varargs.size() != other.varargs.size()) 1264414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey return true; 1278568db534118fc14cc28100306d51626464ff319Jesse Wilson 12843be174888684ef3404a43d8434015193c656cceJeff Sharkey for (size_t i = 0; i < varargs.size(); ++i) 12943be174888684ef3404a43d8434015193c656cceJeff Sharkey if (varargs[i] != other.varargs[i]) 1304414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey return true; 131a2496de37abda981ba80d74f529943374c9d6e3dChristopher Tate 132a2496de37abda981ba80d74f529943374c9d6e3dChristopher Tate return false; 133a2496de37abda981ba80d74f529943374c9d6e3dChristopher Tate } 134a2496de37abda981ba80d74f529943374c9d6e3dChristopher Tate } 135a2496de37abda981ba80d74f529943374c9d6e3dChristopher Tate }; 136a2496de37abda981ba80d74f529943374c9d6e3dChristopher Tate 137a2496de37abda981ba80d74f529943374c9d6e3dChristopher Tate class VISIBILITY_HIDDEN ValueTable { 138a2496de37abda981ba80d74f529943374c9d6e3dChristopher Tate private: 139a2496de37abda981ba80d74f529943374c9d6e3dChristopher Tate DenseMap<Value*, uint32_t> valueNumbering; 140a2496de37abda981ba80d74f529943374c9d6e3dChristopher Tate DenseMap<Expression, uint32_t> expressionNumbering; 141eaef351afcd586d5a84e80455f12f72fd12213efAlon Albert AliasAnalysis* AA; 142eaef351afcd586d5a84e80455f12f72fd12213efAlon Albert MemoryDependenceAnalysis* MD; 143eaef351afcd586d5a84e80455f12f72fd12213efAlon Albert DominatorTree* DT; 144dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 145dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey uint32_t nextValueNumber; 146eaef351afcd586d5a84e80455f12f72fd12213efAlon Albert 147eaef351afcd586d5a84e80455f12f72fd12213efAlon Albert Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 148eaef351afcd586d5a84e80455f12f72fd12213efAlon Albert Expression::ExpressionOpcode getOpcode(CmpInst* C); 149eaef351afcd586d5a84e80455f12f72fd12213efAlon Albert Expression::ExpressionOpcode getOpcode(CastInst* C); 150eaef351afcd586d5a84e80455f12f72fd12213efAlon Albert Expression create_expression(BinaryOperator* BO); 151dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey Expression create_expression(CmpInst* C); 152dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey Expression create_expression(ShuffleVectorInst* V); 153dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey Expression create_expression(ExtractElementInst* C); 154dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey Expression create_expression(InsertElementInst* V); 155dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey Expression create_expression(SelectInst* V); 156dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey Expression create_expression(CastInst* C); 15743be174888684ef3404a43d8434015193c656cceJeff Sharkey Expression create_expression(GetElementPtrInst* G); 1588568db534118fc14cc28100306d51626464ff319Jesse Wilson Expression create_expression(CallInst* C); 15943be174888684ef3404a43d8434015193c656cceJeff Sharkey Expression create_expression(Constant* C); 16043be174888684ef3404a43d8434015193c656cceJeff Sharkey public: 16143be174888684ef3404a43d8434015193c656cceJeff Sharkey ValueTable() : nextValueNumber(1) { } 16243be174888684ef3404a43d8434015193c656cceJeff Sharkey uint32_t lookup_or_add(Value* V); 16343be174888684ef3404a43d8434015193c656cceJeff Sharkey uint32_t lookup(Value* V) const; 16443be174888684ef3404a43d8434015193c656cceJeff Sharkey void add(Value* V, uint32_t num); 16543be174888684ef3404a43d8434015193c656cceJeff Sharkey void clear(); 16643be174888684ef3404a43d8434015193c656cceJeff Sharkey void erase(Value* v); 16743be174888684ef3404a43d8434015193c656cceJeff Sharkey unsigned size(); 16843be174888684ef3404a43d8434015193c656cceJeff Sharkey void setAliasAnalysis(AliasAnalysis* A) { AA = A; } 16943be174888684ef3404a43d8434015193c656cceJeff Sharkey AliasAnalysis *getAliasAnalysis() const { return AA; } 17043be174888684ef3404a43d8434015193c656cceJeff Sharkey void setMemDep(MemoryDependenceAnalysis* M) { MD = M; } 17143be174888684ef3404a43d8434015193c656cceJeff Sharkey void setDomTree(DominatorTree* D) { DT = D; } 172dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey uint32_t getNextUnusedValueNumber() { return nextValueNumber; } 17343be174888684ef3404a43d8434015193c656cceJeff Sharkey }; 174a2496de37abda981ba80d74f529943374c9d6e3dChristopher Tate} 17543be174888684ef3404a43d8434015193c656cceJeff Sharkey 1768568db534118fc14cc28100306d51626464ff319Jesse Wilsonnamespace llvm { 17743be174888684ef3404a43d8434015193c656cceJeff Sharkeytemplate <> struct DenseMapInfo<Expression> { 17843be174888684ef3404a43d8434015193c656cceJeff Sharkey static inline Expression getEmptyKey() { 17943be174888684ef3404a43d8434015193c656cceJeff Sharkey return Expression(Expression::EMPTY); 180a2496de37abda981ba80d74f529943374c9d6e3dChristopher Tate } 18143be174888684ef3404a43d8434015193c656cceJeff Sharkey 1828568db534118fc14cc28100306d51626464ff319Jesse Wilson static inline Expression getTombstoneKey() { 18343be174888684ef3404a43d8434015193c656cceJeff Sharkey return Expression(Expression::TOMBSTONE); 18443be174888684ef3404a43d8434015193c656cceJeff Sharkey } 18543be174888684ef3404a43d8434015193c656cceJeff Sharkey 18643be174888684ef3404a43d8434015193c656cceJeff Sharkey static unsigned getHashValue(const Expression e) { 18743be174888684ef3404a43d8434015193c656cceJeff Sharkey unsigned hash = e.opcode; 18843be174888684ef3404a43d8434015193c656cceJeff Sharkey 18943be174888684ef3404a43d8434015193c656cceJeff Sharkey hash = e.firstVN + hash * 37; 19043be174888684ef3404a43d8434015193c656cceJeff Sharkey hash = e.secondVN + hash * 37; 1914414cea13908b8230640f84ef39603d68ff9c377Jeff Sharkey hash = e.thirdVN + hash * 37; 19243be174888684ef3404a43d8434015193c656cceJeff Sharkey 19343be174888684ef3404a43d8434015193c656cceJeff Sharkey hash = ((unsigned)((uintptr_t)e.type >> 4) ^ 19443be174888684ef3404a43d8434015193c656cceJeff Sharkey (unsigned)((uintptr_t)e.type >> 9)) + 1958568db534118fc14cc28100306d51626464ff319Jesse Wilson hash * 37; 19643be174888684ef3404a43d8434015193c656cceJeff Sharkey 19743be174888684ef3404a43d8434015193c656cceJeff Sharkey for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), 19843be174888684ef3404a43d8434015193c656cceJeff Sharkey E = e.varargs.end(); I != E; ++I) 19943be174888684ef3404a43d8434015193c656cceJeff Sharkey hash = *I + hash * 37; 20043be174888684ef3404a43d8434015193c656cceJeff Sharkey 20143be174888684ef3404a43d8434015193c656cceJeff Sharkey hash = ((unsigned)((uintptr_t)e.function >> 4) ^ 2028568db534118fc14cc28100306d51626464ff319Jesse Wilson (unsigned)((uintptr_t)e.function >> 9)) + 20343be174888684ef3404a43d8434015193c656cceJeff Sharkey hash * 37; 20443be174888684ef3404a43d8434015193c656cceJeff Sharkey 20543be174888684ef3404a43d8434015193c656cceJeff Sharkey return hash; 206eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey } 207eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey static bool isEqual(const Expression &LHS, const Expression &RHS) { 208eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey return LHS == RHS; 209eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey } 210eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey static bool isPod() { return true; } 211eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey}; 212eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey} 213eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey 214eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey//===----------------------------------------------------------------------===// 215eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey// ValueTable Internal Functions 216eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey//===----------------------------------------------------------------------===// 217eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff SharkeyExpression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) { 218a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey switch(BO->getOpcode()) { 219eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey default: // THIS SHOULD NEVER HAPPEN 220eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey assert(0 && "Binary operator with unknown opcode?"); 221eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey case Instruction::Add: return Expression::ADD; 222eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey case Instruction::Sub: return Expression::SUB; 223eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey case Instruction::Mul: return Expression::MUL; 224eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey case Instruction::UDiv: return Expression::UDIV; 225eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey case Instruction::SDiv: return Expression::SDIV; 226eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey case Instruction::FDiv: return Expression::FDIV; 227eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey case Instruction::URem: return Expression::UREM; 228eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey case Instruction::SRem: return Expression::SREM; 229eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey case Instruction::FRem: return Expression::FREM; 230eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey case Instruction::Shl: return Expression::SHL; 231eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey case Instruction::LShr: return Expression::LSHR; 232eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey case Instruction::AShr: return Expression::ASHR; 233eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey case Instruction::And: return Expression::AND; 234eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey case Instruction::Or: return Expression::OR; 2355a7bcf31a44d9875ca5fc010dc213aa2bd5b1168Jeff Sharkey case Instruction::Xor: return Expression::XOR; 2365a7bcf31a44d9875ca5fc010dc213aa2bd5b1168Jeff Sharkey } 2375a7bcf31a44d9875ca5fc010dc213aa2bd5b1168Jeff Sharkey} 23863abc37356728c0575d6a62a203102ae6d97953bJeff Sharkey 2395a7bcf31a44d9875ca5fc010dc213aa2bd5b1168Jeff SharkeyExpression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 2405a7bcf31a44d9875ca5fc010dc213aa2bd5b1168Jeff Sharkey if (isa<ICmpInst>(C) || isa<VICmpInst>(C)) { 241eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey switch (C->getPredicate()) { 242eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey default: // THIS SHOULD NEVER HAPPEN 243eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey assert(0 && "Comparison with unknown predicate?"); 244eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey case ICmpInst::ICMP_EQ: return Expression::ICMPEQ; 245558a23200697d306b75750cf4612cf0717e73537Jeff Sharkey case ICmpInst::ICMP_NE: return Expression::ICMPNE; 246558a23200697d306b75750cf4612cf0717e73537Jeff Sharkey case ICmpInst::ICMP_UGT: return Expression::ICMPUGT; 247558a23200697d306b75750cf4612cf0717e73537Jeff Sharkey case ICmpInst::ICMP_UGE: return Expression::ICMPUGE; 248558a23200697d306b75750cf4612cf0717e73537Jeff Sharkey case ICmpInst::ICMP_ULT: return Expression::ICMPULT; 249558a23200697d306b75750cf4612cf0717e73537Jeff Sharkey case ICmpInst::ICMP_ULE: return Expression::ICMPULE; 250558a23200697d306b75750cf4612cf0717e73537Jeff Sharkey case ICmpInst::ICMP_SGT: return Expression::ICMPSGT; 251558a23200697d306b75750cf4612cf0717e73537Jeff Sharkey case ICmpInst::ICMP_SGE: return Expression::ICMPSGE; 252558a23200697d306b75750cf4612cf0717e73537Jeff Sharkey case ICmpInst::ICMP_SLT: return Expression::ICMPSLT; 253558a23200697d306b75750cf4612cf0717e73537Jeff Sharkey case ICmpInst::ICMP_SLE: return Expression::ICMPSLE; 254558a23200697d306b75750cf4612cf0717e73537Jeff Sharkey } 255558a23200697d306b75750cf4612cf0717e73537Jeff Sharkey } 256558a23200697d306b75750cf4612cf0717e73537Jeff Sharkey assert((isa<FCmpInst>(C) || isa<VFCmpInst>(C)) && "Unknown compare"); 257a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey switch (C->getPredicate()) { 258a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey default: // THIS SHOULD NEVER HAPPEN 259a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey assert(0 && "Comparison with unknown predicate?"); 260a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ; 261a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey case FCmpInst::FCMP_OGT: return Expression::FCMPOGT; 262a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey case FCmpInst::FCMP_OGE: return Expression::FCMPOGE; 263a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey case FCmpInst::FCMP_OLT: return Expression::FCMPOLT; 264a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey case FCmpInst::FCMP_OLE: return Expression::FCMPOLE; 265a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey case FCmpInst::FCMP_ONE: return Expression::FCMPONE; 266234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey case FCmpInst::FCMP_ORD: return Expression::FCMPORD; 267a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey case FCmpInst::FCMP_UNO: return Expression::FCMPUNO; 268a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ; 269a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey case FCmpInst::FCMP_UGT: return Expression::FCMPUGT; 270a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey case FCmpInst::FCMP_UGE: return Expression::FCMPUGE; 271a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey case FCmpInst::FCMP_ULT: return Expression::FCMPULT; 272b52e3e55098c4a6e3dbfe19885895411cfb38911Jeff Sharkey case FCmpInst::FCMP_ULE: return Expression::FCMPULE; 273b52e3e55098c4a6e3dbfe19885895411cfb38911Jeff Sharkey case FCmpInst::FCMP_UNE: return Expression::FCMPUNE; 274b52e3e55098c4a6e3dbfe19885895411cfb38911Jeff Sharkey } 275b52e3e55098c4a6e3dbfe19885895411cfb38911Jeff Sharkey} 276b52e3e55098c4a6e3dbfe19885895411cfb38911Jeff Sharkey 277b52e3e55098c4a6e3dbfe19885895411cfb38911Jeff SharkeyExpression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) { 278b52e3e55098c4a6e3dbfe19885895411cfb38911Jeff Sharkey switch(C->getOpcode()) { 279b52e3e55098c4a6e3dbfe19885895411cfb38911Jeff Sharkey default: // THIS SHOULD NEVER HAPPEN 280b52e3e55098c4a6e3dbfe19885895411cfb38911Jeff Sharkey assert(0 && "Cast operator with unknown opcode?"); 281b52e3e55098c4a6e3dbfe19885895411cfb38911Jeff Sharkey case Instruction::Trunc: return Expression::TRUNC; 282b52e3e55098c4a6e3dbfe19885895411cfb38911Jeff Sharkey case Instruction::ZExt: return Expression::ZEXT; 283b52e3e55098c4a6e3dbfe19885895411cfb38911Jeff Sharkey case Instruction::SExt: return Expression::SEXT; 284b52e3e55098c4a6e3dbfe19885895411cfb38911Jeff Sharkey case Instruction::FPToUI: return Expression::FPTOUI; 285a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey case Instruction::FPToSI: return Expression::FPTOSI; 286dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey case Instruction::UIToFP: return Expression::UITOFP; 287dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey case Instruction::SIToFP: return Expression::SITOFP; 288dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey case Instruction::FPTrunc: return Expression::FPTRUNC; 289dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey case Instruction::FPExt: return Expression::FPEXT; 290dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey case Instruction::PtrToInt: return Expression::PTRTOINT; 291dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey case Instruction::IntToPtr: return Expression::INTTOPTR; 292dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey case Instruction::BitCast: return Expression::BITCAST; 293f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff } 294234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey} 295234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 296234766a36af6214644fa8205202287084ca9cf93Jeff SharkeyExpression ValueTable::create_expression(CallInst* C) { 297234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey Expression e; 298234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 299234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.type = C->getType(); 300234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.firstVN = 0; 301f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff e.secondVN = 0; 302f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff e.thirdVN = 0; 303dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey e.function = C->getCalledFunction(); 304dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey e.opcode = Expression::CALL; 305dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 306dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end(); 307dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey I != E; ++I) 308dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey e.varargs.push_back(lookup_or_add(*I)); 309dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 310f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff return e; 311234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey} 312234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 313234766a36af6214644fa8205202287084ca9cf93Jeff SharkeyExpression ValueTable::create_expression(BinaryOperator* BO) { 314234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey Expression e; 315234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 316234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.firstVN = lookup_or_add(BO->getOperand(0)); 317234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.secondVN = lookup_or_add(BO->getOperand(1)); 318f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff e.thirdVN = 0; 319f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff e.function = 0; 320dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey e.type = BO->getType(); 321dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey e.opcode = getOpcode(BO); 322dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 323dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey return e; 324dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey} 325dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 326dddace758239a5c531f1cb9387eba0fd27b93e08Jeff SharkeyExpression ValueTable::create_expression(CmpInst* C) { 327f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff Expression e; 328234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 329234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.firstVN = lookup_or_add(C->getOperand(0)); 330234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.secondVN = lookup_or_add(C->getOperand(1)); 331234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.thirdVN = 0; 332234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.function = 0; 333234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.type = C->getType(); 334234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.opcode = getOpcode(C); 335f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff 336f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff return e; 337dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey} 338dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 339dddace758239a5c531f1cb9387eba0fd27b93e08Jeff SharkeyExpression ValueTable::create_expression(CastInst* C) { 340dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey Expression e; 341dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 342dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey e.firstVN = lookup_or_add(C->getOperand(0)); 343dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey e.secondVN = 0; 344f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff e.thirdVN = 0; 345234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.function = 0; 346234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.type = C->getType(); 347234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.opcode = getOpcode(C); 348234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 349234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey return e; 350234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey} 351234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 352f7d0b01387c10f93bf17981d45087810c80f0902Ken ShirriffExpression ValueTable::create_expression(ShuffleVectorInst* S) { 3534b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey Expression e; 3544b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey 3554b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey e.firstVN = lookup_or_add(S->getOperand(0)); 3564b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey e.secondVN = lookup_or_add(S->getOperand(1)); 3574b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey e.thirdVN = lookup_or_add(S->getOperand(2)); 3584b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey e.function = 0; 3594b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey e.type = S->getType(); 3604b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey e.opcode = Expression::SHUFFLE; 3614b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey 3624b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey return e; 3634b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey} 3644b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey 3654b17a1321db24b1a59c29b580aed7482a43febeeJeff SharkeyExpression ValueTable::create_expression(ExtractElementInst* E) { 3664b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey Expression e; 3674b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey 3684b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey e.firstVN = lookup_or_add(E->getOperand(0)); 3694b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey e.secondVN = lookup_or_add(E->getOperand(1)); 3704b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey e.thirdVN = 0; 3714b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey e.function = 0; 3724b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey e.type = E->getType(); 3734b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey e.opcode = Expression::EXTRACT; 3744b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey 3754b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey return e; 3764b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey} 377dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 378234766a36af6214644fa8205202287084ca9cf93Jeff SharkeyExpression ValueTable::create_expression(InsertElementInst* I) { 379234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey Expression e; 380234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 381227bec49157bc496f7c9e8e8f63c12728a448922Irfan Sheriff e.firstVN = lookup_or_add(I->getOperand(0)); 382dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey e.secondVN = lookup_or_add(I->getOperand(1)); 383234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.thirdVN = lookup_or_add(I->getOperand(2)); 384234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.function = 0; 385234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.type = I->getType(); 386227bec49157bc496f7c9e8e8f63c12728a448922Irfan Sheriff e.opcode = Expression::INSERT; 387dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 388234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey return e; 389234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey} 390234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 391227bec49157bc496f7c9e8e8f63c12728a448922Irfan SheriffExpression ValueTable::create_expression(SelectInst* I) { 392dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey Expression e; 393234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 394234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.firstVN = lookup_or_add(I->getCondition()); 395234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.secondVN = lookup_or_add(I->getTrueValue()); 396227bec49157bc496f7c9e8e8f63c12728a448922Irfan Sheriff e.thirdVN = lookup_or_add(I->getFalseValue()); 397227bec49157bc496f7c9e8e8f63c12728a448922Irfan Sheriff e.function = 0; 398dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey e.type = I->getType(); 399dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey e.opcode = Expression::SELECT; 400dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 401dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey return e; 402dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey} 403dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 404dddace758239a5c531f1cb9387eba0fd27b93e08Jeff SharkeyExpression ValueTable::create_expression(GetElementPtrInst* G) { 405f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff Expression e; 406234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 407234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.firstVN = lookup_or_add(G->getPointerOperand()); 408234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey e.secondVN = 0; 409f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff e.thirdVN = 0; 410f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff e.function = 0; 411dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey e.type = G->getType(); 412dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey e.opcode = Expression::GEP; 413dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 414dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 415dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey I != E; ++I) 416dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey e.varargs.push_back(lookup_or_add(*I)); 417dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 418f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff return e; 419234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey} 420234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 421234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey//===----------------------------------------------------------------------===// 422f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff// ValueTable External Functions 423f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff//===----------------------------------------------------------------------===// 424dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 425dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey/// add - Insert a value into the table with a specified value number. 426dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkeyvoid ValueTable::add(Value* V, uint32_t num) { 427dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey valueNumbering.insert(std::make_pair(V, num)); 428dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey} 429dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 430dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey/// lookup_or_add - Returns the value number for the specified value, assigning 431f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff/// it a new number if it did not have one before. 432234766a36af6214644fa8205202287084ca9cf93Jeff Sharkeyuint32_t ValueTable::lookup_or_add(Value* V) { 433234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 434234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey if (VI != valueNumbering.end()) 435f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff return VI->second; 436f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff 437dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey if (CallInst* C = dyn_cast<CallInst>(V)) { 438dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey if (AA->doesNotAccessMemory(C)) { 439dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey Expression e = create_expression(C); 440dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey 441dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 442dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey if (EI != expressionNumbering.end()) { 443dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey valueNumbering.insert(std::make_pair(V, EI->second)); 444f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff return EI->second; 445234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey } else { 446234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 447234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 448f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff 449f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff return nextValueNumber++; 45092be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey } 45192be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey } else if (AA->onlyReadsMemory(C)) { 45292be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey Expression e = create_expression(C); 45392be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 45492be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey if (expressionNumbering.find(e) == expressionNumbering.end()) { 45545e9ede55f3c5049fed1fc5002bd5084d1cd7eacDianne Hackborn expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 45692be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 457f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff return nextValueNumber++; 45892be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey } 45992be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 460f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff MemDepResult local_dep = MD->getDependency(C); 46192be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 46292be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey if (local_dep.isNone()) { 46392be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 464f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff return nextValueNumber++; 465f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff } 46692be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 46792be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey if (Instruction *LocalDepInst = local_dep.getInst()) { 46892be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey if (!isa<CallInst>(LocalDepInst)) { 46992be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 47092be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey return nextValueNumber++; 47145e9ede55f3c5049fed1fc5002bd5084d1cd7eacDianne Hackborn } 47292be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 473f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff CallInst* local_cdep = cast<CallInst>(LocalDepInst); 47492be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 47592be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey if (local_cdep->getCalledFunction() != C->getCalledFunction() || 476f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff local_cdep->getNumOperands() != C->getNumOperands()) { 47792be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 47892be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey return nextValueNumber++; 47992be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey } 480c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma 481c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma if (!C->getCalledFunction()) { 48292be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 48392be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey return nextValueNumber++; 48492be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey } 48592be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 48692be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey for (unsigned i = 1; i < C->getNumOperands(); ++i) { 48745e9ede55f3c5049fed1fc5002bd5084d1cd7eacDianne Hackborn uint32_t c_vn = lookup_or_add(C->getOperand(i)); 48892be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey uint32_t cd_vn = lookup_or_add(local_cdep->getOperand(i)); 489c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma if (c_vn != cd_vn) { 49092be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 49192be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey return nextValueNumber++; 492c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma } 49392be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey } 49492be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 49592be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey uint32_t v = lookup_or_add(local_cdep); 496c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma valueNumbering.insert(std::make_pair(V, v)); 497c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma return v; 49892be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey } 49992be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 50092be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 50192be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey const MemoryDependenceAnalysis::NonLocalDepInfo &deps = 50292be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey MD->getNonLocalDependency(C); 50345e9ede55f3c5049fed1fc5002bd5084d1cd7eacDianne Hackborn CallInst* cdep = 0; 50492be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 505c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma // Check to see if we have a single dominating call instruction that is 50692be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey // identical to C. 50792be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey for (unsigned i = 0, e = deps.size(); i != e; ++i) { 508c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma const MemoryDependenceAnalysis::NonLocalDepEntry *I = &deps[i]; 50992be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey // Ignore non-local dependencies. 51092be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey if (I->second.isNonLocal()) 51192be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey continue; 512c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma 513c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma // We don't handle non-depedencies. If we already have a call, reject 51445e9ede55f3c5049fed1fc5002bd5084d1cd7eacDianne Hackborn // instruction dependencies. 51592be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey if (I->second.isNone() || cdep != 0) { 51692be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey cdep = 0; 51792be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey break; 518c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma } 51992be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 52092be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey CallInst *NonLocalDepCall = dyn_cast<CallInst>(I->second.getInst()); 52192be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey // FIXME: All duplicated with non-local case. 52292be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey if (NonLocalDepCall && DT->properlyDominates(I->first, C->getParent())){ 523c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma cdep = NonLocalDepCall; 524c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma continue; 52545e9ede55f3c5049fed1fc5002bd5084d1cd7eacDianne Hackborn } 52692be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 52792be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey cdep = 0; 52892be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey break; 529c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma } 53092be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 53192be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey if (!cdep) { 53292be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 53392be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey return nextValueNumber++; 534c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma } 535c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma 53645e9ede55f3c5049fed1fc5002bd5084d1cd7eacDianne Hackborn if (cdep->getCalledFunction() != C->getCalledFunction() || 53792be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey cdep->getNumOperands() != C->getNumOperands()) { 53892be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 53992be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey return nextValueNumber++; 540c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma } 54192be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey if (!C->getCalledFunction()) { 54292be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 54392be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey return nextValueNumber++; 54492be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey } 545c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma for (unsigned i = 1; i < C->getNumOperands(); ++i) { 546c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma uint32_t c_vn = lookup_or_add(C->getOperand(i)); 54745e9ede55f3c5049fed1fc5002bd5084d1cd7eacDianne Hackborn uint32_t cd_vn = lookup_or_add(cdep->getOperand(i)); 54892be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey if (c_vn != cd_vn) { 54992be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 55092be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey return nextValueNumber++; 551c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma } 55292be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey } 55392be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 55492be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey uint32_t v = lookup_or_add(cdep); 55592be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey valueNumbering.insert(std::make_pair(V, v)); 556c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma return v; 557c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma 55845e9ede55f3c5049fed1fc5002bd5084d1cd7eacDianne Hackborn } else { 55992be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 56092be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey return nextValueNumber++; 56192be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey } 562c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 56392be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey Expression e = create_expression(BO); 56492be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 56592be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 56692be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey if (EI != expressionNumbering.end()) { 567c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma valueNumbering.insert(std::make_pair(V, EI->second)); 568c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma return EI->second; 56945e9ede55f3c5049fed1fc5002bd5084d1cd7eacDianne Hackborn } else { 57092be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 57192be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 57292be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 573c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma return nextValueNumber++; 57492be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey } 57592be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 57692be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey Expression e = create_expression(C); 57792be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 578c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 579c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma if (EI != expressionNumbering.end()) { 58045e9ede55f3c5049fed1fc5002bd5084d1cd7eacDianne Hackborn valueNumbering.insert(std::make_pair(V, EI->second)); 58192be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey return EI->second; 58292be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey } else { 58392be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 584c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma valueNumbering.insert(std::make_pair(V, nextValueNumber)); 58592be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 58692be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey return nextValueNumber++; 58792be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey } 58892be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 589c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma Expression e = create_expression(U); 590c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma 59145e9ede55f3c5049fed1fc5002bd5084d1cd7eacDianne Hackborn DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 59292be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey if (EI != expressionNumbering.end()) { 59392be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey valueNumbering.insert(std::make_pair(V, EI->second)); 59492be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey return EI->second; 595c39c1d4dee917560d174f6ba5402e4c6644edd47Ashish Sharma } else { 59692be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 59792be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 59892be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey 59992be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey return nextValueNumber++; 600eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey } 601eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 602eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey Expression e = create_expression(U); 603eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey 604eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 605a63ba59260cd1bb3f5c16e395ace45a61f1d4461Jeff Sharkey if (EI != expressionNumbering.end()) { 606dddace758239a5c531f1cb9387eba0fd27b93e08Jeff Sharkey valueNumbering.insert(std::make_pair(V, EI->second)); 607eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey return EI->second; 608eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey } else { 609234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 610234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 611234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 612234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey return nextValueNumber++; 613234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey } 614234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 615234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey Expression e = create_expression(U); 616234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 617234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 618234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey if (EI != expressionNumbering.end()) { 619234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey valueNumbering.insert(std::make_pair(V, EI->second)); 620234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey return EI->second; 621234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey } else { 622234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 623eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 624eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey 625eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey return nextValueNumber++; 626eedcb9525ba5befee2ba6ebb7a9ee3f13395c2a3Jeff Sharkey } 627234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 628234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey Expression e = create_expression(U); 629234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 630234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 631234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey if (EI != expressionNumbering.end()) { 632234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey valueNumbering.insert(std::make_pair(V, EI->second)); 6334b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey return EI->second; 6344b17a1321db24b1a59c29b580aed7482a43febeeJeff Sharkey } else { 635234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 636234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey valueNumbering.insert(std::make_pair(V, nextValueNumber)); 637234766a36af6214644fa8205202287084ca9cf93Jeff Sharkey 63892be93a94edafb5906e8bc48e6fee9dd07f5049eJeff Sharkey return nextValueNumber++; 639f7d0b01387c10f93bf17981d45087810c80f0902Ken Shirriff } 640 } else if (CastInst* U = dyn_cast<CastInst>(V)) { 641 Expression e = create_expression(U); 642 643 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 644 if (EI != expressionNumbering.end()) { 645 valueNumbering.insert(std::make_pair(V, EI->second)); 646 return EI->second; 647 } else { 648 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 649 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 650 651 return nextValueNumber++; 652 } 653 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 654 Expression e = create_expression(U); 655 656 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 657 if (EI != expressionNumbering.end()) { 658 valueNumbering.insert(std::make_pair(V, EI->second)); 659 return EI->second; 660 } else { 661 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 662 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 663 664 return nextValueNumber++; 665 } 666 } else { 667 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 668 return nextValueNumber++; 669 } 670} 671 672/// lookup - Returns the value number of the specified value. Fails if 673/// the value has not yet been numbered. 674uint32_t ValueTable::lookup(Value* V) const { 675 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 676 assert(VI != valueNumbering.end() && "Value not numbered?"); 677 return VI->second; 678} 679 680/// clear - Remove all entries from the ValueTable 681void ValueTable::clear() { 682 valueNumbering.clear(); 683 expressionNumbering.clear(); 684 nextValueNumber = 1; 685} 686 687/// erase - Remove a value from the value numbering 688void ValueTable::erase(Value* V) { 689 valueNumbering.erase(V); 690} 691 692//===----------------------------------------------------------------------===// 693// GVN Pass 694//===----------------------------------------------------------------------===// 695 696namespace { 697 struct VISIBILITY_HIDDEN ValueNumberScope { 698 ValueNumberScope* parent; 699 DenseMap<uint32_t, Value*> table; 700 701 ValueNumberScope(ValueNumberScope* p) : parent(p) { } 702 }; 703} 704 705namespace { 706 707 class VISIBILITY_HIDDEN GVN : public FunctionPass { 708 bool runOnFunction(Function &F); 709 public: 710 static char ID; // Pass identification, replacement for typeid 711 GVN() : FunctionPass(&ID) { } 712 713 private: 714 MemoryDependenceAnalysis *MD; 715 DominatorTree *DT; 716 717 ValueTable VN; 718 DenseMap<BasicBlock*, ValueNumberScope*> localAvail; 719 720 typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType; 721 PhiMapType phiMap; 722 723 724 // This transformation requires dominator postdominator info 725 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 726 AU.addRequired<DominatorTree>(); 727 AU.addRequired<MemoryDependenceAnalysis>(); 728 AU.addRequired<AliasAnalysis>(); 729 730 AU.addPreserved<DominatorTree>(); 731 AU.addPreserved<AliasAnalysis>(); 732 } 733 734 // Helper fuctions 735 // FIXME: eliminate or document these better 736 bool processLoad(LoadInst* L, 737 DenseMap<Value*, LoadInst*> &lastLoad, 738 SmallVectorImpl<Instruction*> &toErase); 739 bool processInstruction(Instruction* I, 740 DenseMap<Value*, LoadInst*>& lastSeenLoad, 741 SmallVectorImpl<Instruction*> &toErase); 742 bool processNonLocalLoad(LoadInst* L, 743 SmallVectorImpl<Instruction*> &toErase); 744 bool processBlock(DomTreeNode* DTN); 745 Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, 746 DenseMap<BasicBlock*, Value*> &Phis, 747 bool top_level = false); 748 void dump(DenseMap<uint32_t, Value*>& d); 749 bool iterateOnFunction(Function &F); 750 Value* CollapsePhi(PHINode* p); 751 bool isSafeReplacement(PHINode* p, Instruction* inst); 752 bool performPRE(Function& F); 753 Value* lookupNumber(BasicBlock* BB, uint32_t num); 754 bool mergeBlockIntoPredecessor(BasicBlock* BB); 755 void cleanupGlobalSets(); 756 }; 757 758 char GVN::ID = 0; 759} 760 761// createGVNPass - The public interface to this file... 762FunctionPass *llvm::createGVNPass() { return new GVN(); } 763 764static RegisterPass<GVN> X("gvn", 765 "Global Value Numbering"); 766 767void GVN::dump(DenseMap<uint32_t, Value*>& d) { 768 printf("{\n"); 769 for (DenseMap<uint32_t, Value*>::iterator I = d.begin(), 770 E = d.end(); I != E; ++I) { 771 printf("%d\n", I->first); 772 I->second->dump(); 773 } 774 printf("}\n"); 775} 776 777Value* GVN::CollapsePhi(PHINode* p) { 778 Value* constVal = p->hasConstantValue(); 779 if (!constVal) return 0; 780 781 Instruction* inst = dyn_cast<Instruction>(constVal); 782 if (!inst) 783 return constVal; 784 785 if (DT->dominates(inst, p)) 786 if (isSafeReplacement(p, inst)) 787 return inst; 788 return 0; 789} 790 791bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) { 792 if (!isa<PHINode>(inst)) 793 return true; 794 795 for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end(); 796 UI != E; ++UI) 797 if (PHINode* use_phi = dyn_cast<PHINode>(UI)) 798 if (use_phi->getParent() == inst->getParent()) 799 return false; 800 801 return true; 802} 803 804/// GetValueForBlock - Get the value to use within the specified basic block. 805/// available values are in Phis. 806Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, 807 DenseMap<BasicBlock*, Value*> &Phis, 808 bool top_level) { 809 810 // If we have already computed this value, return the previously computed val. 811 DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 812 if (V != Phis.end() && !top_level) return V->second; 813 814 // If the block is unreachable, just return undef, since this path 815 // can't actually occur at runtime. 816 if (!DT->isReachableFromEntry(BB)) 817 return Phis[BB] = UndefValue::get(orig->getType()); 818 819 BasicBlock* singlePred = BB->getSinglePredecessor(); 820 if (singlePred) { 821 Value *ret = GetValueForBlock(singlePred, orig, Phis); 822 Phis[BB] = ret; 823 return ret; 824 } 825 826 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 827 // now, then get values to fill in the incoming values for the PHI. 828 PHINode *PN = PHINode::Create(orig->getType(), orig->getName()+".rle", 829 BB->begin()); 830 PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 831 832 if (Phis.count(BB) == 0) 833 Phis.insert(std::make_pair(BB, PN)); 834 835 // Fill in the incoming values for the block. 836 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 837 Value* val = GetValueForBlock(*PI, orig, Phis); 838 PN->addIncoming(val, *PI); 839 } 840 841 VN.getAliasAnalysis()->copyValue(orig, PN); 842 843 // Attempt to collapse PHI nodes that are trivially redundant 844 Value* v = CollapsePhi(PN); 845 if (!v) { 846 // Cache our phi construction results 847 phiMap[orig->getPointerOperand()].insert(PN); 848 return PN; 849 } 850 851 PN->replaceAllUsesWith(v); 852 853 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 854 E = Phis.end(); I != E; ++I) 855 if (I->second == PN) 856 I->second = v; 857 858 DEBUG(cerr << "GVN removed: " << *PN); 859 MD->removeInstruction(PN); 860 PN->eraseFromParent(); 861 862 Phis[BB] = v; 863 return v; 864} 865 866/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are 867/// non-local by performing PHI construction. 868bool GVN::processNonLocalLoad(LoadInst* L, 869 SmallVectorImpl<Instruction*> &toErase) { 870 // Find the non-local dependencies of the load 871 const MemoryDependenceAnalysis::NonLocalDepInfo &deps = 872 MD->getNonLocalDependency(L); 873 DEBUG(cerr << "INVESTIGATING NONLOCAL LOAD: " << deps.size() << *L); 874#if 0 875 DEBUG(for (unsigned i = 0, e = deps.size(); i != e; ++i) { 876 cerr << " " << deps[i].first->getName(); 877 if (Instruction *I = deps[i].second.getInst()) 878 cerr << *I; 879 else 880 cerr << "\n"; 881 }); 882#endif 883 884 // If we had to process more than one hundred blocks to find the 885 // dependencies, this load isn't worth worrying about. Optimizing 886 // it will be too expensive. 887 if (deps.size() > 100) 888 return false; 889 890 BasicBlock *EntryBlock = &L->getParent()->getParent()->getEntryBlock(); 891 892 DenseMap<BasicBlock*, Value*> repl; 893 894 // Filter out useless results (non-locals, etc) 895 for (unsigned i = 0, e = deps.size(); i != e; ++i) { 896 BasicBlock *DepBB = deps[i].first; 897 MemDepResult DepInfo = deps[i].second; 898 899 if (DepInfo.isNonLocal()) { 900 // If this is a non-local dependency in the entry block, then we depend on 901 // the value live-in at the start of the function. We could insert a load 902 // in the entry block to get this, but for now we'll just bail out. 903 // 904 // FIXME: Consider emitting a load in the entry block to catch this case! 905 // Tricky part is to sink so that it doesn't execute in places where it 906 // isn't needed. 907 if (DepBB == EntryBlock) 908 return false; 909 continue; 910 } 911 912 if (DepInfo.isNone()) { 913 repl[DepBB] = UndefValue::get(L->getType()); 914 continue; 915 } 916 917 if (StoreInst* S = dyn_cast<StoreInst>(DepInfo.getInst())) { 918 // Reject loads and stores that are to the same address but are of 919 // different types. 920 // NOTE: 403.gcc does have this case (e.g. in readonly_fields_p) because 921 // of bitfield access, it would be interesting to optimize for it at some 922 // point. 923 if (S->getOperand(0)->getType() != L->getType()) 924 return false; 925 926 if (S->getPointerOperand() != L->getPointerOperand() && 927 VN.getAliasAnalysis()->alias(S->getPointerOperand(), 1, 928 L->getPointerOperand(), 1) 929 != AliasAnalysis::MustAlias) 930 return false; 931 repl[DepBB] = S->getOperand(0); 932 } else if (LoadInst* LD = dyn_cast<LoadInst>(DepInfo.getInst())) { 933 if (LD->getType() != L->getType()) 934 return false; 935 936 if (LD->getPointerOperand() != L->getPointerOperand() && 937 VN.getAliasAnalysis()->alias(LD->getPointerOperand(), 1, 938 L->getPointerOperand(), 1) 939 != AliasAnalysis::MustAlias) 940 return false; 941 repl[DepBB] = LD; 942 } else { 943 return false; 944 } 945 } 946 947 // Use cached PHI construction information from previous runs 948 SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()]; 949 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 950 I != E; ++I) { 951 if ((*I)->getParent() == L->getParent()) { 952 L->replaceAllUsesWith(*I); 953 toErase.push_back(L); 954 NumGVNLoad++; 955 return true; 956 } 957 958 repl.insert(std::make_pair((*I)->getParent(), *I)); 959 } 960 961 DEBUG(cerr << "GVN REMOVING NONLOCAL LOAD: " << *L); 962 963 // Perform PHI construction 964 SmallPtrSet<BasicBlock*, 4> visited; 965 Value* v = GetValueForBlock(L->getParent(), L, repl, true); 966 L->replaceAllUsesWith(v); 967 toErase.push_back(L); 968 NumGVNLoad++; 969 return true; 970} 971 972/// processLoad - Attempt to eliminate a load, first by eliminating it 973/// locally, and then attempting non-local elimination if that fails. 974bool GVN::processLoad(LoadInst *L, DenseMap<Value*, LoadInst*> &lastLoad, 975 SmallVectorImpl<Instruction*> &toErase) { 976 if (L->isVolatile()) { 977 lastLoad[L->getPointerOperand()] = L; 978 return false; 979 } 980 981 Value* pointer = L->getPointerOperand(); 982 LoadInst*& last = lastLoad[pointer]; 983 984 // ... to a pointer that has been loaded from before... 985 bool removedNonLocal = false; 986 MemDepResult dep = MD->getDependency(L); 987 if (dep.isNonLocal() && 988 L->getParent() != &L->getParent()->getParent()->getEntryBlock()) { 989 removedNonLocal = processNonLocalLoad(L, toErase); 990 991 if (!removedNonLocal) 992 last = L; 993 994 return removedNonLocal; 995 } 996 997 998 bool deletedLoad = false; 999 1000 // Walk up the dependency chain until we either find 1001 // a dependency we can use, or we can't walk any further 1002 while (Instruction *DepInst = dep.getInst()) { 1003 // ... that depends on a store ... 1004 if (StoreInst* S = dyn_cast<StoreInst>(DepInst)) { 1005 if (S->getPointerOperand() == pointer) { 1006 // Remove it! 1007 L->replaceAllUsesWith(S->getOperand(0)); 1008 toErase.push_back(L); 1009 deletedLoad = true; 1010 NumGVNLoad++; 1011 } 1012 1013 // Whether we removed it or not, we can't 1014 // go any further 1015 break; 1016 } else if (!isa<LoadInst>(DepInst)) { 1017 // Only want to handle loads below. 1018 break; 1019 } else if (!last) { 1020 // If we don't depend on a store, and we haven't 1021 // been loaded before, bail. 1022 break; 1023 } else if (DepInst == last) { 1024 // Remove it! 1025 L->replaceAllUsesWith(last); 1026 toErase.push_back(L); 1027 deletedLoad = true; 1028 NumGVNLoad++; 1029 break; 1030 } else { 1031 dep = MD->getDependencyFrom(L, DepInst, DepInst->getParent()); 1032 } 1033 } 1034 1035 // If this load really doesn't depend on anything, then we must be loading an 1036 // undef value. This can happen when loading for a fresh allocation with no 1037 // intervening stores, for example. 1038 if (dep.isNone()) { 1039 // If this load depends directly on an allocation, there isn't 1040 // anything stored there; therefore, we can optimize this load 1041 // to undef. 1042 L->replaceAllUsesWith(UndefValue::get(L->getType())); 1043 toErase.push_back(L); 1044 deletedLoad = true; 1045 NumGVNLoad++; 1046 } 1047 1048 if (!deletedLoad) 1049 last = L; 1050 1051 return deletedLoad; 1052} 1053 1054Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) { 1055 DenseMap<BasicBlock*, ValueNumberScope*>::iterator I = localAvail.find(BB); 1056 if (I == localAvail.end()) 1057 return 0; 1058 1059 ValueNumberScope* locals = I->second; 1060 1061 while (locals) { 1062 DenseMap<uint32_t, Value*>::iterator I = locals->table.find(num); 1063 if (I != locals->table.end()) 1064 return I->second; 1065 else 1066 locals = locals->parent; 1067 } 1068 1069 return 0; 1070} 1071 1072/// processInstruction - When calculating availability, handle an instruction 1073/// by inserting it into the appropriate sets 1074bool GVN::processInstruction(Instruction *I, 1075 DenseMap<Value*, LoadInst*> &lastSeenLoad, 1076 SmallVectorImpl<Instruction*> &toErase) { 1077 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 1078 bool changed = processLoad(L, lastSeenLoad, toErase); 1079 1080 if (!changed) { 1081 unsigned num = VN.lookup_or_add(L); 1082 localAvail[I->getParent()]->table.insert(std::make_pair(num, L)); 1083 } 1084 1085 return changed; 1086 } 1087 1088 uint32_t nextNum = VN.getNextUnusedValueNumber(); 1089 unsigned num = VN.lookup_or_add(I); 1090 1091 // Allocations are always uniquely numbered, so we can save time and memory 1092 // by fast failing them. 1093 if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) { 1094 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1095 return false; 1096 } 1097 1098 // Collapse PHI nodes 1099 if (PHINode* p = dyn_cast<PHINode>(I)) { 1100 Value* constVal = CollapsePhi(p); 1101 1102 if (constVal) { 1103 for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end(); 1104 PI != PE; ++PI) 1105 if (PI->second.count(p)) 1106 PI->second.erase(p); 1107 1108 p->replaceAllUsesWith(constVal); 1109 toErase.push_back(p); 1110 } else { 1111 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1112 } 1113 1114 // If the number we were assigned was a brand new VN, then we don't 1115 // need to do a lookup to see if the number already exists 1116 // somewhere in the domtree: it can't! 1117 } else if (num == nextNum) { 1118 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1119 1120 // Perform value-number based elimination 1121 } else if (Value* repl = lookupNumber(I->getParent(), num)) { 1122 // Remove it! 1123 VN.erase(I); 1124 I->replaceAllUsesWith(repl); 1125 toErase.push_back(I); 1126 return true; 1127 } else { 1128 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1129 } 1130 1131 return false; 1132} 1133 1134// GVN::runOnFunction - This is the main transformation entry point for a 1135// function. 1136// 1137bool GVN::runOnFunction(Function& F) { 1138 MD = &getAnalysis<MemoryDependenceAnalysis>(); 1139 DT = &getAnalysis<DominatorTree>(); 1140 VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>()); 1141 VN.setMemDep(MD); 1142 VN.setDomTree(DT); 1143 1144 bool changed = false; 1145 bool shouldContinue = true; 1146 1147 // Merge unconditional branches, allowing PRE to catch more 1148 // optimization opportunities. 1149 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) { 1150 BasicBlock* BB = FI; 1151 ++FI; 1152 bool removedBlock = MergeBlockIntoPredecessor(BB, this); 1153 if (removedBlock) NumGVNBlocks++; 1154 1155 changed |= removedBlock; 1156 } 1157 1158 while (shouldContinue) { 1159 shouldContinue = iterateOnFunction(F); 1160 changed |= shouldContinue; 1161 } 1162 1163 if (EnablePRE) { 1164 bool PREChanged = true; 1165 while (PREChanged) { 1166 PREChanged = performPRE(F); 1167 changed |= PREChanged; 1168 } 1169 } 1170 1171 cleanupGlobalSets(); 1172 1173 return changed; 1174} 1175 1176 1177bool GVN::processBlock(DomTreeNode* DTN) { 1178 BasicBlock* BB = DTN->getBlock(); 1179 SmallVector<Instruction*, 8> toErase; 1180 DenseMap<Value*, LoadInst*> lastSeenLoad; 1181 bool changed_function = false; 1182 1183 if (DTN->getIDom()) 1184 localAvail[BB] = 1185 new ValueNumberScope(localAvail[DTN->getIDom()->getBlock()]); 1186 else 1187 localAvail[BB] = new ValueNumberScope(0); 1188 1189 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1190 BI != BE;) { 1191 changed_function |= processInstruction(BI, lastSeenLoad, toErase); 1192 if (toErase.empty()) { 1193 ++BI; 1194 continue; 1195 } 1196 1197 // If we need some instructions deleted, do it now. 1198 NumGVNInstr += toErase.size(); 1199 1200 // Avoid iterator invalidation. 1201 bool AtStart = BI == BB->begin(); 1202 if (!AtStart) 1203 --BI; 1204 1205 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 1206 E = toErase.end(); I != E; ++I) { 1207 DEBUG(cerr << "GVN removed: " << **I); 1208 MD->removeInstruction(*I); 1209 (*I)->eraseFromParent(); 1210 } 1211 1212 if (AtStart) 1213 BI = BB->begin(); 1214 else 1215 ++BI; 1216 1217 toErase.clear(); 1218 } 1219 1220 return changed_function; 1221} 1222 1223/// performPRE - Perform a purely local form of PRE that looks for diamond 1224/// control flow patterns and attempts to perform simple PRE at the join point. 1225bool GVN::performPRE(Function& F) { 1226 bool changed = false; 1227 SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit; 1228 DenseMap<BasicBlock*, Value*> predMap; 1229 for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()), 1230 DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) { 1231 BasicBlock* CurrentBlock = *DI; 1232 1233 // Nothing to PRE in the entry block. 1234 if (CurrentBlock == &F.getEntryBlock()) continue; 1235 1236 for (BasicBlock::iterator BI = CurrentBlock->begin(), 1237 BE = CurrentBlock->end(); BI != BE; ) { 1238 if (isa<AllocationInst>(BI) || isa<TerminatorInst>(BI) || 1239 isa<PHINode>(BI) || BI->mayReadFromMemory() || 1240 BI->mayWriteToMemory()) { 1241 BI++; 1242 continue; 1243 } 1244 1245 uint32_t valno = VN.lookup(BI); 1246 1247 // Look for the predecessors for PRE opportunities. We're 1248 // only trying to solve the basic diamond case, where 1249 // a value is computed in the successor and one predecessor, 1250 // but not the other. We also explicitly disallow cases 1251 // where the successor is its own predecessor, because they're 1252 // more complicated to get right. 1253 unsigned numWith = 0; 1254 unsigned numWithout = 0; 1255 BasicBlock* PREPred = 0; 1256 predMap.clear(); 1257 1258 for (pred_iterator PI = pred_begin(CurrentBlock), 1259 PE = pred_end(CurrentBlock); PI != PE; ++PI) { 1260 // We're not interested in PRE where the block is its 1261 // own predecessor, on in blocks with predecessors 1262 // that are not reachable. 1263 if (*PI == CurrentBlock) { 1264 numWithout = 2; 1265 break; 1266 } else if (!localAvail.count(*PI)) { 1267 numWithout = 2; 1268 break; 1269 } 1270 1271 DenseMap<uint32_t, Value*>::iterator predV = 1272 localAvail[*PI]->table.find(valno); 1273 if (predV == localAvail[*PI]->table.end()) { 1274 PREPred = *PI; 1275 numWithout++; 1276 } else if (predV->second == BI) { 1277 numWithout = 2; 1278 } else { 1279 predMap[*PI] = predV->second; 1280 numWith++; 1281 } 1282 } 1283 1284 // Don't do PRE when it might increase code size, i.e. when 1285 // we would need to insert instructions in more than one pred. 1286 if (numWithout != 1 || numWith == 0) { 1287 BI++; 1288 continue; 1289 } 1290 1291 // We can't do PRE safely on a critical edge, so instead we schedule 1292 // the edge to be split and perform the PRE the next time we iterate 1293 // on the function. 1294 unsigned succNum = 0; 1295 for (unsigned i = 0, e = PREPred->getTerminator()->getNumSuccessors(); 1296 i != e; ++i) 1297 if (PREPred->getTerminator()->getSuccessor(i) == CurrentBlock) { 1298 succNum = i; 1299 break; 1300 } 1301 1302 if (isCriticalEdge(PREPred->getTerminator(), succNum)) { 1303 toSplit.push_back(std::make_pair(PREPred->getTerminator(), succNum)); 1304 changed = true; 1305 BI++; 1306 continue; 1307 } 1308 1309 // Instantiate the expression the in predecessor that lacked it. 1310 // Because we are going top-down through the block, all value numbers 1311 // will be available in the predecessor by the time we need them. Any 1312 // that weren't original present will have been instantiated earlier 1313 // in this loop. 1314 Instruction* PREInstr = BI->clone(); 1315 bool success = true; 1316 for (unsigned i = 0; i < BI->getNumOperands(); ++i) { 1317 Value* op = BI->getOperand(i); 1318 if (isa<Argument>(op) || isa<Constant>(op) || isa<GlobalValue>(op)) 1319 PREInstr->setOperand(i, op); 1320 else { 1321 Value* V = lookupNumber(PREPred, VN.lookup(op)); 1322 if (!V) { 1323 success = false; 1324 break; 1325 } else 1326 PREInstr->setOperand(i, V); 1327 } 1328 } 1329 1330 // Fail out if we encounter an operand that is not available in 1331 // the PRE predecessor. This is typically because of loads which 1332 // are not value numbered precisely. 1333 if (!success) { 1334 delete PREInstr; 1335 BI++; 1336 continue; 1337 } 1338 1339 PREInstr->insertBefore(PREPred->getTerminator()); 1340 PREInstr->setName(BI->getName() + ".pre"); 1341 predMap[PREPred] = PREInstr; 1342 VN.add(PREInstr, valno); 1343 NumGVNPRE++; 1344 1345 // Update the availability map to include the new instruction. 1346 localAvail[PREPred]->table.insert(std::make_pair(valno, PREInstr)); 1347 1348 // Create a PHI to make the value available in this block. 1349 PHINode* Phi = PHINode::Create(BI->getType(), 1350 BI->getName() + ".pre-phi", 1351 CurrentBlock->begin()); 1352 for (pred_iterator PI = pred_begin(CurrentBlock), 1353 PE = pred_end(CurrentBlock); PI != PE; ++PI) 1354 Phi->addIncoming(predMap[*PI], *PI); 1355 1356 VN.add(Phi, valno); 1357 localAvail[CurrentBlock]->table[valno] = Phi; 1358 1359 BI->replaceAllUsesWith(Phi); 1360 VN.erase(BI); 1361 1362 Instruction* erase = BI; 1363 BI++; 1364 DEBUG(cerr << "GVN PRE removed: " << *erase); 1365 MD->removeInstruction(erase); 1366 erase->eraseFromParent(); 1367 changed = true; 1368 } 1369 } 1370 1371 for (SmallVector<std::pair<TerminatorInst*, unsigned>, 4>::iterator 1372 I = toSplit.begin(), E = toSplit.end(); I != E; ++I) 1373 SplitCriticalEdge(I->first, I->second, this); 1374 1375 return changed || toSplit.size(); 1376} 1377 1378// iterateOnFunction - Executes one iteration of GVN 1379bool GVN::iterateOnFunction(Function &F) { 1380 cleanupGlobalSets(); 1381 1382 // Top-down walk of the dominator tree 1383 bool changed = false; 1384 for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()), 1385 DE = df_end(DT->getRootNode()); DI != DE; ++DI) 1386 changed |= processBlock(*DI); 1387 1388 return changed; 1389} 1390 1391void GVN::cleanupGlobalSets() { 1392 VN.clear(); 1393 phiMap.clear(); 1394 1395 for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator 1396 I = localAvail.begin(), E = localAvail.end(); I != E; ++I) 1397 delete I->second; 1398 localAvail.clear(); 1399} 1400