119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===// 219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The LLVM Compiler Infrastructure 419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file is distributed under the University of Illinois Open Source 619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// License. See LICENSE.TXT for details. 719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This pass performs a simple dominator tree walk that eliminates trivially 1119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// redundant instructions. 1219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 1419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#define DEBUG_TYPE "early-cse" 1619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Transforms/Scalar.h" 1719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Instructions.h" 1819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Pass.h" 1919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Analysis/Dominators.h" 2019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Analysis/InstructionSimplify.h" 2119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Target/TargetData.h" 2219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Transforms/Utils/Local.h" 2319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/Debug.h" 2419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/RecyclingAllocator.h" 2519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/ScopedHashTable.h" 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/Statistic.h" 2719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanusing namespace llvm; 2819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 2919bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumSimplify, "Number of instructions simplified or DCE'd"); 3019bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumCSE, "Number of instructions CSE'd"); 3119bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumCSELoad, "Number of load instructions CSE'd"); 3219bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumCSECall, "Number of call instructions CSE'd"); 3319bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumDSE, "Number of trivial dead stores removed"); 3419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic unsigned getHash(const void *V) { 3619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return DenseMapInfo<const void*>::getHashValue(V); 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// SimpleValue 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 4219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace { 4419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// SimpleValue - Instances of this struct represent available values in the 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// scoped hash table. 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman struct SimpleValue { 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *Inst; 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SimpleValue(Instruction *I) : Inst(I) { 5019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert((isSentinel() || canHandle(I)) && "Inst can't be handled!"); 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isSentinel() const { 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Inst == DenseMapInfo<Instruction*>::getEmptyKey() || 5519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Inst == DenseMapInfo<Instruction*>::getTombstoneKey(); 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static bool canHandle(Instruction *Inst) { 5919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This can only handle non-void readnone functions. 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CallInst *CI = dyn_cast<CallInst>(Inst)) 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy(); 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) || 6319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) || 6419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) || 6519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) || 6619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst); 6719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 6819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 6919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 7019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace llvm { 7219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// SimpleValue is POD. 7319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate<> struct isPodLike<SimpleValue> { 7419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static const bool value = true; 7519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 7619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate<> struct DenseMapInfo<SimpleValue> { 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static inline SimpleValue getEmptyKey() { 7919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return DenseMapInfo<Instruction*>::getEmptyKey(); 8019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 8119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static inline SimpleValue getTombstoneKey() { 8219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return DenseMapInfo<Instruction*>::getTombstoneKey(); 8319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static unsigned getHashValue(SimpleValue Val); 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static bool isEqual(SimpleValue LHS, SimpleValue RHS); 8619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 8719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 8819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanunsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) { 9019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *Inst = Val.Inst; 9119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Hash in all of the operands as pointers. 9319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Res = 0; 9419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i) 9519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Res ^= getHash(Inst->getOperand(i)) << (i & 0xF); 9619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CastInst *CI = dyn_cast<CastInst>(Inst)) 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Res ^= getHash(CI->getType()); 9919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) 10019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Res ^= CI->getPredicate(); 10119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst)) { 10219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (ExtractValueInst::idx_iterator I = EVI->idx_begin(), 10319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman E = EVI->idx_end(); I != E; ++I) 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Res ^= *I; 10519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst)) { 10619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (InsertValueInst::idx_iterator I = IVI->idx_begin(), 10719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman E = IVI->idx_end(); I != E; ++I) 10819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Res ^= *I; 10919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 11019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // nothing extra to hash in. 11119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert((isa<CallInst>(Inst) || 11219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isa<BinaryOperator>(Inst) || isa<GetElementPtrInst>(Inst) || 11319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) || 11419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst)) && 11519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Invalid/unknown instruction"); 11619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 11719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Mix in the opcode. 11919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return (Res << 1) ^ Inst->getOpcode(); 12019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 12119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) { 12319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst; 12419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LHS.isSentinel() || RHS.isSentinel()) 12619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return LHSI == RHSI; 12719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LHSI->getOpcode() != RHSI->getOpcode()) return false; 12919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return LHSI->isIdenticalTo(RHSI); 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 13119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 13319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// CallValue 13419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 13519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace { 13719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// CallValue - Instances of this struct represent available call values in 13819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// the scoped hash table. 13919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman struct CallValue { 14019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *Inst; 14119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CallValue(Instruction *I) : Inst(I) { 14319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert((isSentinel() || canHandle(I)) && "Inst can't be handled!"); 14419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 14519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isSentinel() const { 14719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Inst == DenseMapInfo<Instruction*>::getEmptyKey() || 14819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Inst == DenseMapInfo<Instruction*>::getTombstoneKey(); 14919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 15019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static bool canHandle(Instruction *Inst) { 15219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Don't value number anything that returns void. 15319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Inst->getType()->isVoidTy()) 15419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 15519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CallInst *CI = dyn_cast<CallInst>(Inst); 15719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CI == 0 || !CI->onlyReadsMemory()) 15819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 15919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 16019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 16119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 16219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 16319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace llvm { 16519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // CallValue is POD. 16619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman template<> struct isPodLike<CallValue> { 16719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static const bool value = true; 16819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 16919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 17019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman template<> struct DenseMapInfo<CallValue> { 17119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static inline CallValue getEmptyKey() { 17219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return DenseMapInfo<Instruction*>::getEmptyKey(); 17319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 17419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static inline CallValue getTombstoneKey() { 17519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return DenseMapInfo<Instruction*>::getTombstoneKey(); 17619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 17719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static unsigned getHashValue(CallValue Val); 17819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static bool isEqual(CallValue LHS, CallValue RHS); 17919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 18019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 18119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanunsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) { 18219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *Inst = Val.Inst; 18319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Hash in all of the operands as pointers. 18419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Res = 0; 18519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i) { 18619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!Inst->getOperand(i)->getType()->isMetadataTy() && 18719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Cannot value number calls with metadata operands"); 18819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Res ^= getHash(Inst->getOperand(i)) << (i & 0xF); 18919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 19019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Mix in the opcode. 19219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return (Res << 1) ^ Inst->getOpcode(); 19319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 19419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) { 19619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst; 19719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LHS.isSentinel() || RHS.isSentinel()) 19819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return LHSI == RHSI; 19919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return LHSI->isIdenticalTo(RHSI); 20019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 20119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 20419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// EarlyCSE pass. 20519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 20619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace { 20819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// EarlyCSE - This pass does a simple depth-first walk over the dominator 21019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// tree, eliminating trivially redundant instructions and using instsimplify 21119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// to canonicalize things as it goes. It is intended to be fast and catch 21219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// obvious cases so that instcombine and other passes are more effective. It 21319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// is expected that a later pass of GVN will catch the interesting/hard 21419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// cases. 21519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass EarlyCSE : public FunctionPass { 21619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 21719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetData *TD; 21819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DominatorTree *DT; 21919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef RecyclingAllocator<BumpPtrAllocator, 22019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ScopedHashTableVal<SimpleValue, Value*> > AllocatorTy; 22119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef ScopedHashTable<SimpleValue, Value*, DenseMapInfo<SimpleValue>, 22219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AllocatorTy> ScopedHTType; 22319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 22419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// AvailableValues - This scoped hash table contains the current values of 22519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// all of our simple scalar expressions. As we walk down the domtree, we 22619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// look to see if instructions are in this: if so, we replace them with what 22719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// we find, otherwise we insert them so that dominated values can succeed in 22819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// their lookup. 22919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ScopedHTType *AvailableValues; 23019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 23119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// AvailableLoads - This scoped hash table contains the current values 23219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// of loads. This allows us to get efficient access to dominating loads when 23319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// we have a fully redundant load. In addition to the most recent load, we 23419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// keep track of a generation count of the read, which is compared against 23519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// the current generation count. The current generation count is 23619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// incremented after every possibly writing memory operation, which ensures 23719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// that we only CSE loads with other loads that have no intervening store. 23819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef RecyclingAllocator<BumpPtrAllocator, 23919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ScopedHashTableVal<Value*, std::pair<Value*, unsigned> > > LoadMapAllocator; 24019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef ScopedHashTable<Value*, std::pair<Value*, unsigned>, 24119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DenseMapInfo<Value*>, LoadMapAllocator> LoadHTType; 24219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoadHTType *AvailableLoads; 24319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 24419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// AvailableCalls - This scoped hash table contains the current values 24519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// of read-only call values. It uses the same generation count as loads. 24619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef ScopedHashTable<CallValue, std::pair<Value*, unsigned> > CallHTType; 24719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CallHTType *AvailableCalls; 24819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 24919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// CurrentGeneration - This is the current generation of the memory value. 25019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned CurrentGeneration; 25119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 25219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static char ID; 25319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman explicit EarlyCSE() : FunctionPass(ID) { 25419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman initializeEarlyCSEPass(*PassRegistry::getPassRegistry()); 25519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 25619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 25719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool runOnFunction(Function &F); 25819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 25919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanprivate: 26019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool processNode(DomTreeNode *Node); 26219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This transformation requires dominator postdominator info 26419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 26519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addRequired<DominatorTree>(); 26619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.setPreservesCFG(); 26719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 26819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 26919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 27019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 27119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanchar EarlyCSE::ID = 0; 27219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 27319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// createEarlyCSEPass - The public interface to this file. 27419bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanFunctionPass *llvm::createEarlyCSEPass() { 27519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return new EarlyCSE(); 27619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 27719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 27819bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false) 27919bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(DominatorTree) 28019bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false) 28119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 28219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool EarlyCSE::processNode(DomTreeNode *Node) { 28319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Define a scope in the scoped hash table. When we are done processing this 28419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // domtree node and recurse back up to our parent domtree node, this will pop 28519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // off all the values we install. 28619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ScopedHTType::ScopeTy Scope(*AvailableValues); 28719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 28819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Define a scope for the load values so that anything we add will get 28919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // popped when we recurse back up to our parent domtree node. 29019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoadHTType::ScopeTy LoadScope(*AvailableLoads); 29119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 29219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Define a scope for the call values so that anything we add will get 29319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // popped when we recurse back up to our parent domtree node. 29419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CallHTType::ScopeTy CallScope(*AvailableCalls); 29519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 29619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *BB = Node->getBlock(); 29719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 29819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this block has a single predecessor, then the predecessor is the parent 29919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // of the domtree node and all of the live out memory values are still current 30019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // in this block. If this block has multiple predecessors, then they could 30119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // have invalidated the live-out memory values of our parent value. For now, 30219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // just be conservative and invalidate memory if this block has multiple 30319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // predecessors. 30419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BB->getSinglePredecessor() == 0) 30519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++CurrentGeneration; 30619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// LastStore - Keep track of the last non-volatile store that we saw... for 30819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// as long as there in no instruction that reads memory. If we see a store 30919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// to the same location, we delete the dead store. This zaps trivial dead 31019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// stores which can occur in bitfield code among other things. 31119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman StoreInst *LastStore = 0; 31219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 31319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool Changed = false; 31419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 31519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // See if any instructions in the block can be eliminated. If so, do it. If 31619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // not, add them to AvailableValues. 31719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 31819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *Inst = I++; 31919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Dead instructions should just be removed. 32119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isInstructionTriviallyDead(Inst)) { 32219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n'); 32319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Inst->eraseFromParent(); 32419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Changed = true; 32519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumSimplify; 32619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 32719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 32819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the instruction can be simplified (e.g. X+0 = X) then replace it with 33019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // its simpler value. 33119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Value *V = SimplifyInstruction(Inst, TD, DT)) { 33219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << " to: " << *V << '\n'); 33319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Inst->replaceAllUsesWith(V); 33419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Inst->eraseFromParent(); 33519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Changed = true; 33619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumSimplify; 33719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 33819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 33919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 34019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this is a simple instruction that we can value number, process it. 34119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SimpleValue::canHandle(Inst)) { 34219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // See if the instruction has an available value. If so, use it. 34319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Value *V = AvailableValues->lookup(Inst)) { 34419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << " to: " << *V << '\n'); 34519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Inst->replaceAllUsesWith(V); 34619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Inst->eraseFromParent(); 34719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Changed = true; 34819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumCSE; 34919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 35019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 35119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 35219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Otherwise, just remember that this value is available. 35319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AvailableValues->insert(Inst, Inst); 35419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 35519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 35619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 35719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this is a non-volatile load, process it. 35819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 35919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Ignore volatile loads. 36019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!LI->isSimple()) { 36119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LastStore = 0; 36219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 36319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 36419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 36519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If we have an available version of this load, and if it is the right 36619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // generation, replace this instruction. 36719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::pair<Value*, unsigned> InVal = 36819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AvailableLoads->lookup(Inst->getOperand(0)); 36919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (InVal.first != 0 && InVal.second == CurrentGeneration) { 37019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst << " to: " 37119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << *InVal.first << '\n'); 37219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first); 37319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Inst->eraseFromParent(); 37419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Changed = true; 37519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumCSELoad; 37619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 37719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 37819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 37919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Otherwise, remember that we have this instruction. 38019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AvailableLoads->insert(Inst->getOperand(0), 38119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::pair<Value*, unsigned>(Inst, CurrentGeneration)); 38219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LastStore = 0; 38319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 38419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 38519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 38619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this instruction may read from memory, forget LastStore. 38719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Inst->mayReadFromMemory()) 38819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LastStore = 0; 38919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 39019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this is a read-only call, process it. 39119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CallValue::canHandle(Inst)) { 39219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If we have an available version of this call, and if it is the right 39319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // generation, replace this instruction. 39419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::pair<Value*, unsigned> InVal = AvailableCalls->lookup(Inst); 39519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (InVal.first != 0 && InVal.second == CurrentGeneration) { 39619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst << " to: " 39719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << *InVal.first << '\n'); 39819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first); 39919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Inst->eraseFromParent(); 40019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Changed = true; 40119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumCSECall; 40219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 40319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 40419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 40519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Otherwise, remember that we have this instruction. 40619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AvailableCalls->insert(Inst, 40719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::pair<Value*, unsigned>(Inst, CurrentGeneration)); 40819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 40919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 41019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 41119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Okay, this isn't something we can CSE at all. Check to see if it is 41219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // something that could modify memory. If so, our available memory values 41319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // cannot be used so bump the generation count. 41419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Inst->mayWriteToMemory()) { 41519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++CurrentGeneration; 41619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 41719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 41819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We do a trivial form of DSE if there are two stores to the same 41919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // location with no intervening loads. Delete the earlier store. 42019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LastStore && 42119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LastStore->getPointerOperand() == SI->getPointerOperand()) { 42219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore << " due to: " 42319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << *Inst << '\n'); 42419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LastStore->eraseFromParent(); 42519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Changed = true; 42619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumDSE; 42719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LastStore = 0; 42819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 42919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 43019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 43119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Okay, we just invalidated anything we knew about loaded values. Try 43219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // to salvage *something* by remembering that the stored value is a live 43319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // version of the pointer. It is safe to forward from volatile stores 43419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // to non-volatile loads, so we don't have to check for volatility of 43519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the store. 43619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AvailableLoads->insert(SI->getPointerOperand(), 43719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::pair<Value*, unsigned>(SI->getValueOperand(), CurrentGeneration)); 43819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 43919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Remember that this was the last store we saw for DSE. 44019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SI->isSimple()) 44119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LastStore = SI; 44219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 44319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 44419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 44519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 44619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned LiveOutGeneration = CurrentGeneration; 44719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I) { 44819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Changed |= processNode(*I); 44919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Pop any generation changes off the stack from the recursive walk. 45019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurrentGeneration = LiveOutGeneration; 45119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 45219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Changed; 45319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 45419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 45519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 45619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool EarlyCSE::runOnFunction(Function &F) { 45719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TD = getAnalysisIfAvailable<TargetData>(); 45819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DT = &getAnalysis<DominatorTree>(); 45919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 46019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Tables that the pass uses when walking the domtree. 46119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ScopedHTType AVTable; 46219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AvailableValues = &AVTable; 46319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoadHTType LoadTable; 46419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AvailableLoads = &LoadTable; 46519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CallHTType CallTable; 46619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AvailableCalls = &CallTable; 46719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 46819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurrentGeneration = 0; 46919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return processNode(DT->getRootNode()); 47019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 471