CodeGenPrepare.cpp revision 75abc1ed0618048c3cf6c5b71c9868c10d6c1478
1dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner//===- CodeGenPrepare.cpp - Prepare a function for code generation --------===// 2dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// 3dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// The LLVM Compiler Infrastructure 4dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// 5dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// This file was developed by Chris Lattner and is distributed under 6dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// the University of Illinois Open Source License. See LICENSE.TXT for details. 7dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// 8dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner//===----------------------------------------------------------------------===// 9dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// 10dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// This pass munges the code in the input function to better prepare it for 11dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// SelectionDAG-based code generation. This works around limitations in it's 12dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// basic-block-at-a-time approach. It should eventually be removed. 13dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// 14dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner//===----------------------------------------------------------------------===// 15dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 16dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#define DEBUG_TYPE "codegenprepare" 17dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Transforms/Scalar.h" 18dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Constants.h" 19dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/DerivedTypes.h" 20dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Function.h" 21dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Instructions.h" 22dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Pass.h" 23dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetAsmInfo.h" 24dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetData.h" 25dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetLowering.h" 26dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetMachine.h" 27dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 28dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Transforms/Utils/Local.h" 29dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/ADT/DenseMap.h" 30dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/ADT/SmallSet.h" 31d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner#include "llvm/Support/Debug.h" 32d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner#include "llvm/Support/Compiler.h" 33dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 34dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerusing namespace llvm; 35dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 36dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnernamespace { 37dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner class VISIBILITY_HIDDEN CodeGenPrepare : public FunctionPass { 38dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// TLI - Keep a pointer of a TargetLowering to consult for determining 39dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// transformation profitability. 40dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner const TargetLowering *TLI; 41dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner public: 42dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CodeGenPrepare(const TargetLowering *tli = 0) : TLI(tli) {} 43dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool runOnFunction(Function &F); 44dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 45dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner private: 46d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool EliminateMostlyEmptyBlocks(Function &F); 47d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; 48d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner void EliminateMostlyEmptyBlock(BasicBlock *BB); 49dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool OptimizeBlock(BasicBlock &BB); 50dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool OptimizeLoadStoreInst(Instruction *I, Value *Addr, 51dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const Type *AccessTy, 52dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DenseMap<Value*,Value*> &SunkAddrs); 53dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner }; 54dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 55dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerstatic RegisterPass<CodeGenPrepare> X("codegenprepare", 56dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner "Optimize for code generation"); 57dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 58dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris LattnerFunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { 59dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return new CodeGenPrepare(TLI); 60dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 61dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 62dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 63dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::runOnFunction(Function &F) { 64dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool EverMadeChange = false; 65d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 66d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // First pass, eliminate blocks that contain only PHI nodes and an 67d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // unconditional branch. 68d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EverMadeChange |= EliminateMostlyEmptyBlocks(F); 69d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 70d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = true; 71dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner while (MadeChange) { 72dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = false; 73dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 74dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange |= OptimizeBlock(*BB); 75dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner EverMadeChange |= MadeChange; 76dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 77dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return EverMadeChange; 78dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 79dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 80d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes 81d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// and an unconditional branch. Passes before isel (e.g. LSR/loopsimplify) 82d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// often split edges in ways that are non-optimal for isel. Start by 83d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// eliminating these blocks so we can split them the way we want them. 84d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) { 85d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = false; 86d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Note that this intentionally skips the entry block. 87d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) { 88d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *BB = I++; 89d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 90d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If this block doesn't end with an uncond branch, ignore it. 91d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 92d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!BI || !BI->isUnconditional()) 93d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 94d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 95d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If the instruction before the branch isn't a phi node, then other stuff 96d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // is happening here. 97d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::iterator BBI = BI; 98d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBI != BB->begin()) { 99d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner --BBI; 100d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!isa<PHINode>(BBI)) continue; 101d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 102d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 103d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Do not break infinite loops. 104d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 105d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (DestBB == BB) 106d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 107d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 108d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!CanMergeBlocks(BB, DestBB)) 109d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 110d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 111d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EliminateMostlyEmptyBlock(BB); 112d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner MadeChange = true; 113d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 114d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return MadeChange; 115d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 116d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 117d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a 118d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// single uncond branch between them, and BB contains no other non-phi 119d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// instructions. 120d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, 121d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const BasicBlock *DestBB) const { 122d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // We only want to eliminate blocks whose phi nodes are used by phi nodes in 123d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // the successor. If there are more complex condition (e.g. preheaders), 124d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // don't mess around with them. 125d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::const_iterator BBI = BB->begin(); 126d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 127d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (Value::use_const_iterator UI = PN->use_begin(), E = PN->use_end(); 128d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner UI != E; ++UI) { 129d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Instruction *User = cast<Instruction>(*UI); 130d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (User->getParent() != DestBB || !isa<PHINode>(User)) 131d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return false; 13275abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel // If User is inside DestBB block and it is a PHINode then check 13375abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel // incoming value. If incoming value is not from BB then this is 13475abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel // a complex condition (e.g. preheaders) we want to avoid here. 13575abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (User->getParent() == DestBB) { 13675abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (const PHINode *UPN = dyn_cast<PHINode>(User)) 13775abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { 13875abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); 13975abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (Insn && Insn->getParent() == BB && 14075abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Insn->getParent() != UPN->getIncomingBlock(I)) 14175abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel return false; 14275abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 14375abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 144d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 145d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 146d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 147d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If BB and DestBB contain any common predecessors, then the phi nodes in BB 148d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // and DestBB may have conflicting incoming values for the block. If so, we 149d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // can't merge the block. 150d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); 151d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!DestBBPN) return true; // no conflict. 152d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 153d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Collect the preds of BB. 154d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner SmallPtrSet<BasicBlock*, 16> BBPreds; 155d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 156d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // It is faster to get preds from a PHI than with pred_iterator. 157d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 158d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(BBPN->getIncomingBlock(i)); 159d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 160d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(pred_begin(BB), pred_end(BB)); 161d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 162d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 163d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Walk the preds of DestBB. 164d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { 165d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *Pred = DestBBPN->getIncomingBlock(i); 166d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBPreds.count(Pred)) { // Common predecessor? 167d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBI = DestBB->begin(); 168d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 169d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V1 = PN->getIncomingValueForBlock(Pred); 170d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V2 = PN->getIncomingValueForBlock(BB); 171d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 172d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If V2 is a phi node in BB, look up what the mapped value will be. 173d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) 174d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V2PN->getParent() == BB) 175d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner V2 = V2PN->getIncomingValueForBlock(Pred); 176d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 177d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If there is a conflict, bail out. 178d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V1 != V2) return false; 179d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 180d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 181d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 182d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 183d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return true; 184d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 185d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 186d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 187d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and 188d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// an unconditional branch in it. 189d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnervoid CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { 190d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 191d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 192d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 193d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner DOUT << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB; 194d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 195d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If the destination block has a single pred, then this is a trivial edge, 196d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // just collapse it. 197d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (DestBB->getSinglePredecessor()) { 198d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If DestBB has single-entry PHI nodes, fold them. 199d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 200d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 201d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->eraseFromParent(); 202d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 203d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 204d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Splice all the PHI nodes from BB over to DestBB. 205d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner DestBB->getInstList().splice(DestBB->begin(), BB->getInstList(), 206d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->begin(), BI); 207d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 208d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Anything that branched to BB now branches to DestBB. 209d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->replaceAllUsesWith(DestBB); 210d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 211d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Nuke BB. 212d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->eraseFromParent(); 213d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 214d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner DOUT << "AFTER:\n" << *DestBB << "\n\n\n"; 215d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return; 216d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 217d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 218d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB 219d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // to handle the new incoming edges it is about to have. 220d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *PN; 221d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (BasicBlock::iterator BBI = DestBB->begin(); 222d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 223d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Remove the incoming value for BB, and remember it. 224d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner Value *InVal = PN->removeIncomingValue(BB, false); 225d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 226d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Two options: either the InVal is a phi node defined in BB or it is some 227d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // value that dominates BB. 228d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *InValPhi = dyn_cast<PHINode>(InVal); 229d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (InValPhi && InValPhi->getParent() == BB) { 230d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Add all of the input values of the input PHI as inputs of this phi. 231d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) 232d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InValPhi->getIncomingValue(i), 233d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner InValPhi->getIncomingBlock(i)); 234d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 235d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, add one instance of the dominating value for each edge that 236d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // we will be adding. 237d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 238d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 239d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); 240d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 241d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 242d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, *PI); 243d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 244d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 245d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 246d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 247d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // The PHIs are now updated, change everything that refers to BB to use 248d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // DestBB and remove BB. 249d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->replaceAllUsesWith(DestBB); 250d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->eraseFromParent(); 251d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 252d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner DOUT << "AFTER:\n" << *DestBB << "\n\n\n"; 253d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 254d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 255d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 256dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// SplitEdgeNicely - Split the critical edge from TI to it's specified 257dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// successor if it will improve codegen. We only do this if the successor has 258dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// phi nodes (otherwise critical edges are ok). If there is already another 259dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// predecessor of the succ that is empty (and thus has no phi nodes), use it 260dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// instead of introducing a new block. 261dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerstatic void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, Pass *P) { 262dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *TIBB = TI->getParent(); 263dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *Dest = TI->getSuccessor(SuccNum); 264dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner assert(isa<PHINode>(Dest->begin()) && 265dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner "This should only be called if Dest has a PHI!"); 266dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 267dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// TIPHIValues - This array is lazily computed to determine the values of 268dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// PHIs in Dest that TI would provide. 269dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner std::vector<Value*> TIPHIValues; 270dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 271dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Check to see if Dest has any blocks that can be used as a split edge for 272dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // this terminator. 273dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (pred_iterator PI = pred_begin(Dest), E = pred_end(Dest); PI != E; ++PI) { 274dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *Pred = *PI; 275dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // To be usable, the pred has to end with an uncond branch to the dest. 276dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator()); 277dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (!PredBr || !PredBr->isUnconditional() || 278dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Must be empty other than the branch. 279dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner &Pred->front() != PredBr) 280dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner continue; 281dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 282dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Finally, since we know that Dest has phi nodes in it, we have to make 283dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // sure that jumping to Pred will have the same affect as going to Dest in 284dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // terms of PHI values. 285dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner PHINode *PN; 286dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner unsigned PHINo = 0; 287dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool FoundMatch = true; 288dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (BasicBlock::iterator I = Dest->begin(); 289dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) { 290dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (PHINo == TIPHIValues.size()) 291dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TIPHIValues.push_back(PN->getIncomingValueForBlock(TIBB)); 292dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 293dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If the PHI entry doesn't work, we can't use this pred. 294dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (TIPHIValues[PHINo] != PN->getIncomingValueForBlock(Pred)) { 295dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner FoundMatch = false; 296dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner break; 297dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 298dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 299dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 300dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we found a workable predecessor, change TI to branch to Succ. 301dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (FoundMatch) { 302dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Dest->removePredecessor(TIBB); 303dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TI->setSuccessor(SuccNum, Pred); 304dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return; 305dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 306dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 307dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 308dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner SplitCriticalEdge(TI, SuccNum, P, true); 309dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 310dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 311dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// OptimizeNoopCopyExpression - If the specified cast instruction is a noop 312dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// copy (e.g. it's casting from one pointer type to another, int->uint, or 313dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// int->sbyte on PPC), sink it into user blocks to reduce the number of virtual 314dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// registers that must be created and coallesced. 315dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// 316dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// Return true if any changes are made. 317dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){ 318dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is a noop copy, 319dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner MVT::ValueType SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 320dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner MVT::ValueType DstVT = TLI.getValueType(CI->getType()); 321dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 322dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This is an fp<->int conversion? 323dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (MVT::isInteger(SrcVT) != MVT::isInteger(DstVT)) 324dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 325dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 326dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is an extension, it will be a zero or sign extension, which 327dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // isn't a noop. 328dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SrcVT < DstVT) return false; 329dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 330dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If these values will be promoted, find out what they will be promoted 331dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // to. This helps us consider truncates on PPC as noop copies when they 332dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // are. 333dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) 334dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SrcVT = TLI.getTypeToTransformTo(SrcVT); 335dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.getTypeAction(DstVT) == TargetLowering::Promote) 336dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DstVT = TLI.getTypeToTransformTo(DstVT); 337dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 338dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If, after promotion, these are the same types, this is a noop copy. 339dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SrcVT != DstVT) 340dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 341dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 342dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *DefBB = CI->getParent(); 343dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 344dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// InsertedCasts - Only insert a cast in each block once. 345dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner std::map<BasicBlock*, CastInst*> InsertedCasts; 346dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 347dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 348dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 349dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner UI != E; ) { 350dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Use &TheUse = UI.getUse(); 351dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *User = cast<Instruction>(*UI); 352dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 353dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Figure out which BB this cast is used in. For PHI's this is the 354dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // appropriate predecessor block. 355dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *UserBB = User->getParent(); 356dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) { 357dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner unsigned OpVal = UI.getOperandNo()/2; 358dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner UserBB = PN->getIncomingBlock(OpVal); 359dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 360dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 361dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Preincrement use iterator so we don't invalidate it. 362dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner ++UI; 363dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 364dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If this user is in the same block as the cast, don't change the cast. 365dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (UserBB == DefBB) continue; 366dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 367dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we have already inserted a cast into this block, use it. 368dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CastInst *&InsertedCast = InsertedCasts[UserBB]; 369dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 370dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (!InsertedCast) { 371dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock::iterator InsertPt = UserBB->begin(); 372dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner while (isa<PHINode>(InsertPt)) ++InsertPt; 373dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 374dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner InsertedCast = 375dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CastInst::create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 376dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner InsertPt); 377dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = true; 378dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 379dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 380dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Replace a use of the cast with a use of the new casat. 381dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TheUse = InsertedCast; 382dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 383dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 384dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we removed all uses, nuke the cast. 385dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (CI->use_empty()) 386dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CI->eraseFromParent(); 387dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 388dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 389dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 390dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 391dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// EraseDeadInstructions - Erase any dead instructions 392dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic void EraseDeadInstructions(Value *V) { 393dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Instruction *I = dyn_cast<Instruction>(V); 394dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!I || !I->use_empty()) return; 395dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 396dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SmallPtrSet<Instruction*, 16> Insts; 397dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Insts.insert(I); 398dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 399dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner while (!Insts.empty()) { 400dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner I = *Insts.begin(); 401dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Insts.erase(I); 402dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (isInstructionTriviallyDead(I)) { 403dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 404dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i))) 405dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Insts.insert(U); 406dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner I->eraseFromParent(); 407dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 408dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 409dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 410dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 411dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 412dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// ExtAddrMode - This is an extended version of TargetLowering::AddrMode which 413dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// holds actual Value*'s for register values. 414dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstruct ExtAddrMode : public TargetLowering::AddrMode { 415dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *BaseReg; 416dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *ScaledReg; 417dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ExtAddrMode() : BaseReg(0), ScaledReg(0) {} 418dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner void dump() const; 419dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner}; 420dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 421dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic std::ostream &operator<<(std::ostream &OS, const ExtAddrMode &AM) { 422dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool NeedPlus = false; 423dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner OS << "["; 424dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AM.BaseGV) 425dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner OS << (NeedPlus ? " + " : "") 426dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner << "GV:%" << AM.BaseGV->getName(), NeedPlus = true; 427dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 428dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AM.BaseOffs) 429dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner OS << (NeedPlus ? " + " : "") << AM.BaseOffs, NeedPlus = true; 430dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 431dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AM.BaseReg) 432dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner OS << (NeedPlus ? " + " : "") 433dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner << "Base:%" << AM.BaseReg->getName(), NeedPlus = true; 434dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AM.Scale) 435dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner OS << (NeedPlus ? " + " : "") 436dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner << AM.Scale << "*%" << AM.ScaledReg->getName(), NeedPlus = true; 437dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 438dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return OS << "]"; 439dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 440dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 441dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnervoid ExtAddrMode::dump() const { 442dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cerr << *this << "\n"; 443dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 444dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 445dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool TryMatchingScaledValue(Value *ScaleReg, int64_t Scale, 446dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const Type *AccessTy, ExtAddrMode &AddrMode, 447dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SmallVector<Instruction*, 16> &AddrModeInsts, 448dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const TargetLowering &TLI, unsigned Depth); 449dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 450dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// FindMaximalLegalAddressingMode - If we can, try to merge the computation of 451dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// Addr into the specified addressing mode. If Addr can't be added to AddrMode 452dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// this returns false. This assumes that Addr is either a pointer type or 453dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// intptr_t for the target. 454dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool FindMaximalLegalAddressingMode(Value *Addr, const Type *AccessTy, 455dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ExtAddrMode &AddrMode, 456dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SmallVector<Instruction*, 16> &AddrModeInsts, 457dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const TargetLowering &TLI, 458dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner unsigned Depth) { 459dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 460dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is a global variable, fold it into the addressing mode if possible. 461dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (GlobalValue *GV = dyn_cast<GlobalValue>(Addr)) { 462dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseGV == 0) { 463dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseGV = GV; 464dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 465dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 466dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseGV = 0; 467dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 468dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (ConstantInt *CI = dyn_cast<ConstantInt>(Addr)) { 469dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseOffs += CI->getSExtValue(); 470dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 471dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 472dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseOffs -= CI->getSExtValue(); 473dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (isa<ConstantPointerNull>(Addr)) { 474dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 475dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 476dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 477dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Look through constant exprs and instructions. 478dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner unsigned Opcode = ~0U; 479dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner User *AddrInst = 0; 480dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast<Instruction>(Addr)) { 481dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Opcode = I->getOpcode(); 482dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrInst = I; 483dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) { 484dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Opcode = CE->getOpcode(); 485dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrInst = CE; 486dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 487dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 488dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Limit recursion to avoid exponential behavior. 489dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Depth == 5) { AddrInst = 0; Opcode = ~0U; } 490dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 491dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is really an instruction, add it to our list of related 492dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // instructions. 493dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast_or_null<Instruction>(AddrInst)) 494dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts.push_back(I); 495dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 496dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner switch (Opcode) { 497dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::PtrToInt: 498dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // PtrToInt is always a noop, as we know that the int type is pointer sized. 499dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, 500dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, Depth)) 501dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 502dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 503dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::IntToPtr: 504dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This inttoptr is a no-op if the integer type is pointer sized. 505dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.getValueType(AddrInst->getOperand(0)->getType()) == 506dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner TLI.getPointerTy()) { 507dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, 508dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, Depth)) 509dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 510dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 511dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 512dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::Add: { 513dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if we can merge in the RHS then the LHS. If so, we win. 514dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ExtAddrMode BackupAddrMode = AddrMode; 515dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner unsigned OldSize = AddrModeInsts.size(); 516dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (FindMaximalLegalAddressingMode(AddrInst->getOperand(1), AccessTy, 517dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, Depth+1) && 518dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, 519dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, Depth+1)) 520dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 521dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 522dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Restore the old addr mode info. 523dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode = BackupAddrMode; 524dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts.resize(OldSize); 525dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 526dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Otherwise this was over-aggressive. Try merging in the LHS then the RHS. 527dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, 528dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, Depth+1) && 529dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner FindMaximalLegalAddressingMode(AddrInst->getOperand(1), AccessTy, 530dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, Depth+1)) 531dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 532dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 533dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Otherwise we definitely can't merge the ADD in. 534dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode = BackupAddrMode; 535dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts.resize(OldSize); 536dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 537dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 538dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::Or: { 539dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1)); 540dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!RHS) break; 541dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD. 542dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 543dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 544dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::Mul: 545dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::Shl: { 546dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Can only handle X*C and X << C, and can only handle this when the scale 547dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // field is available. 548dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1)); 549dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!RHS) break; 550dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner int64_t Scale = RHS->getSExtValue(); 551dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Opcode == Instruction::Shl) 552dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Scale = 1 << Scale; 553dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 554dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TryMatchingScaledValue(AddrInst->getOperand(0), Scale, AccessTy, 555dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, Depth)) 556dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 557dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 558dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 559dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::GetElementPtr: { 560dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Scan the GEP. We check it if it contains constant offsets and at most 561dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // one variable offset. 562dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner int VariableOperand = -1; 563dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner unsigned VariableScale = 0; 564dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 565dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner int64_t ConstantOffset = 0; 566dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const TargetData *TD = TLI.getTargetData(); 567dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner gep_type_iterator GTI = gep_type_begin(AddrInst); 568dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) { 569dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (const StructType *STy = dyn_cast<StructType>(*GTI)) { 570dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const StructLayout *SL = TD->getStructLayout(STy); 571dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner unsigned Idx = 572dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue(); 573dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ConstantOffset += SL->getElementOffset(Idx); 574dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 575dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner uint64_t TypeSize = TD->getTypeSize(GTI.getIndexedType()); 576dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(AddrInst->getOperand(i))) { 577dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ConstantOffset += CI->getSExtValue()*TypeSize; 578dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (TypeSize) { // Scales of zero don't do anything. 579dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // We only allow one variable index at the moment. 580dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (VariableOperand != -1) { 581dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner VariableOperand = -2; 582dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 583dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 584dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 585dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Remember the variable index. 586dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner VariableOperand = i; 587dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner VariableScale = TypeSize; 588dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 589dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 590dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 591dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 592dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If the GEP had multiple variable indices, punt. 593dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (VariableOperand == -2) 594dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 595dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 596dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // A common case is for the GEP to only do a constant offset. In this case, 597dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // just add it to the disp field and check validity. 598dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (VariableOperand == -1) { 599dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseOffs += ConstantOffset; 600dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (ConstantOffset == 0 || TLI.isLegalAddressingMode(AddrMode, AccessTy)){ 601dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if we can fold the base pointer in too. 602dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, 603dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, 604dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Depth+1)) 605dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 606dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 607dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseOffs -= ConstantOffset; 608dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 609dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check that this has no base reg yet. If so, we won't have a place to 610dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // put the base of the GEP (assuming it is not a null ptr). 611dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool SetBaseReg = false; 612dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.HasBaseReg) { 613dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!isa<ConstantPointerNull>(AddrInst->getOperand(0))) 614dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 615dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 616dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.HasBaseReg = true; 617dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseReg = AddrInst->getOperand(0); 618dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SetBaseReg = true; 619dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 620dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 621dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // See if the scale amount is valid for this target. 622dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseOffs += ConstantOffset; 623dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TryMatchingScaledValue(AddrInst->getOperand(VariableOperand), 624dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner VariableScale, AccessTy, AddrMode, 625dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts, TLI, Depth)) { 626dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!SetBaseReg) return true; 627dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 628dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this match succeeded, we know that we can form an address with the 629dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // GepBase as the basereg. See if we can match *more*. 630dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.HasBaseReg = false; 631dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseReg = 0; 632dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, 633dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, 634dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Depth+1)) 635dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 636dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Strange, shouldn't happen. Restore the base reg and succeed the easy 637dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // way. 638dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.HasBaseReg = true; 639dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseReg = AddrInst->getOperand(0); 640dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 641dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 642dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 643dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseOffs -= ConstantOffset; 644dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SetBaseReg) { 645dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.HasBaseReg = false; 646dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseReg = 0; 647dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 648dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 649dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 650dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 651dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 652dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 653dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast_or_null<Instruction>(AddrInst)) { 654dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner assert(AddrModeInsts.back() == I && "Stack imbalance"); 655dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts.pop_back(); 656dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 657dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 658dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Worse case, the target should support [reg] addressing modes. :) 659dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!AddrMode.HasBaseReg) { 660dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.HasBaseReg = true; 661dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Still check for legality in case the target supports [imm] but not [i+r]. 662dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) { 663dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseReg = Addr; 664dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 665dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 666dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.HasBaseReg = false; 667dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 668dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 669dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If the base register is already taken, see if we can do [r+r]. 670dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale == 0) { 671dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.Scale = 1; 672dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) { 673dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.ScaledReg = Addr; 674dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 675dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 676dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.Scale = 0; 677dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 678dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Couldn't match. 679dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 680dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 681dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 682dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// TryMatchingScaledValue - Try adding ScaleReg*Scale to the specified 683dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// addressing mode. Return true if this addr mode is legal for the target, 684dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// false if not. 685dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool TryMatchingScaledValue(Value *ScaleReg, int64_t Scale, 686dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const Type *AccessTy, ExtAddrMode &AddrMode, 687dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SmallVector<Instruction*, 16> &AddrModeInsts, 688dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const TargetLowering &TLI, unsigned Depth) { 689dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If we already have a scale of this value, we can add to it, otherwise, we 690dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // need an available scale field. 691dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg) 692dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 693dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 694dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ExtAddrMode InputAddrMode = AddrMode; 695dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 696dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add scale to turn X*4+X*3 -> X*7. This could also do things like 697dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // [A+B + A*7] -> [B+A*8]. 698dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.Scale += Scale; 699dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.ScaledReg = ScaleReg; 700dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 701dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) { 702dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Okay, we decided that we can add ScaleReg+Scale to AddrMode. Check now 703dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // to see if ScaleReg is actually X+C. If so, we can turn this into adding 704dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // X*Scale + C*Scale to addr mode. 705dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner BinaryOperator *BinOp = dyn_cast<BinaryOperator>(ScaleReg); 706dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (BinOp && BinOp->getOpcode() == Instruction::Add && 707dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner isa<ConstantInt>(BinOp->getOperand(1)) && InputAddrMode.ScaledReg ==0) { 708dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 709dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner InputAddrMode.Scale = Scale; 710dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner InputAddrMode.ScaledReg = BinOp->getOperand(0); 711dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner InputAddrMode.BaseOffs += 712dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cast<ConstantInt>(BinOp->getOperand(1))->getSExtValue()*Scale; 713dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.isLegalAddressingMode(InputAddrMode, AccessTy)) { 714dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts.push_back(BinOp); 715dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode = InputAddrMode; 716dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 717dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 718dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 719dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 720dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Otherwise, not (x+c)*scale, just return what we have. 721dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 722dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 723dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 724dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Otherwise, back this attempt out. 725dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.Scale -= Scale; 726dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale == 0) AddrMode.ScaledReg = 0; 727dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 728dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 729dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 730dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 731dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 732dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// IsNonLocalValue - Return true if the specified values are defined in a 733dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// different basic block than BB. 734dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool IsNonLocalValue(Value *V, BasicBlock *BB) { 735dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 736dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return I->getParent() != BB; 737dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 738dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 739dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 740dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// OptimizeLoadStoreInst - Load and Store Instructions have often have 741dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// addressing modes that can do significant amounts of computation. As such, 742dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// instruction selection will try to get the load or store to do as much 743dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// computation as possible for the program. The problem is that isel can only 744dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// see within a single block. As such, we sink as much legal addressing mode 745dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// stuff into the block as possible. 746dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerbool CodeGenPrepare::OptimizeLoadStoreInst(Instruction *LdStInst, Value *Addr, 747dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const Type *AccessTy, 748dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DenseMap<Value*,Value*> &SunkAddrs) { 749dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Figure out what addressing mode will be built up for this operation. 750dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SmallVector<Instruction*, 16> AddrModeInsts; 751dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ExtAddrMode AddrMode; 752dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool Success = FindMaximalLegalAddressingMode(Addr, AccessTy, AddrMode, 753dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts, *TLI, 0); 754dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Success = Success; assert(Success && "Couldn't select *anything*?"); 755dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 756dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if any of the instructions supersumed by this addr mode are 757dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // non-local to I's BB. 758dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool AnyNonLocal = false; 759dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { 760dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (IsNonLocalValue(AddrModeInsts[i], LdStInst->getParent())) { 761dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AnyNonLocal = true; 762dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 763dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 764dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 765dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 766dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If all the instructions matched are already in this BB, don't do anything. 767dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!AnyNonLocal) { 768dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DEBUG(cerr << "CGP: Found local addrmode: " << AddrMode << "\n"); 769dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 770dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 771dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 772dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Insert this computation right after this user. Since our caller is 773dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // scanning from the top of the BB to the bottom, reuse of the expr are 774dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // guaranteed to happen later. 775dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner BasicBlock::iterator InsertPt = LdStInst; 776dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 777dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Now that we determined the addressing expression we want to use and know 778dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // that we have to sink it into this block. Check to see if we have already 779dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done this for some other load/store instr in this block. If so, reuse the 780dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // computation. 781dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *&SunkAddr = SunkAddrs[Addr]; 782dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr) { 783dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DEBUG(cerr << "CGP: Reusing nonlocal addrmode: " << AddrMode << "\n"); 784dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr->getType() != Addr->getType()) 785dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new BitCastInst(SunkAddr, Addr->getType(), "tmp", InsertPt); 786dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 787dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DEBUG(cerr << "CGP: SINKING nonlocal addrmode: " << AddrMode << "\n"); 788dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const Type *IntPtrTy = TLI->getTargetData()->getIntPtrType(); 789dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 790dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *Result = 0; 791dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Start with the scale value. 792dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale) { 793dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = AddrMode.ScaledReg; 794dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (V->getType() == IntPtrTy) { 795dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done. 796dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (isa<PointerType>(V->getType())) { 797dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 798dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 799dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cast<IntegerType>(V->getType())->getBitWidth()) { 800dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new TruncInst(V, IntPtrTy, "sunkaddr", InsertPt); 801dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 802dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new SExtInst(V, IntPtrTy, "sunkaddr", InsertPt); 803dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 804dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale != 1) 805dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = BinaryOperator::createMul(V, ConstantInt::get(IntPtrTy, 806dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.Scale), 807dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner "sunkaddr", InsertPt); 808dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 809dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 810dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 811dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the base register. 812dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseReg) { 813dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = AddrMode.BaseReg; 814dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (V->getType() != IntPtrTy) 815dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 816dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 817dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = BinaryOperator::createAdd(Result, V, "sunkaddr", InsertPt); 818dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 819dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 820dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 821dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 822dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the BaseGV if present. 823dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseGV) { 824dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = new PtrToIntInst(AddrMode.BaseGV, IntPtrTy, "sunkaddr", 825dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner InsertPt); 826dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 827dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = BinaryOperator::createAdd(Result, V, "sunkaddr", InsertPt); 828dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 829dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 830dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 831dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 832dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the Base Offset if present. 833dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseOffs) { 834dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 835dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 836dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = BinaryOperator::createAdd(Result, V, "sunkaddr", InsertPt); 837dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 838dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 839dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 840dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 841dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result == 0) 842dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = Constant::getNullValue(Addr->getType()); 843dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 844dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new IntToPtrInst(Result, Addr->getType(), "sunkaddr",InsertPt); 845dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 846dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 847dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner LdStInst->replaceUsesOfWith(Addr, SunkAddr); 848dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 849dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Addr->use_empty()) 850dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner EraseDeadInstructions(Addr); 851dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 852dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 853dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 854dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// In this pass we look for GEP and cast instructions that are used 855dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// across basic blocks and rewrite them to improve basic-block-at-a-time 856dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// selection. 857dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { 858dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 859dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 860dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Split all critical edges where the dest block has a PHI and where the phi 861dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // has shared immediate operands. 862dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TerminatorInst *BBTI = BB.getTerminator(); 863dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (BBTI->getNumSuccessors() > 1) { 864dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (unsigned i = 0, e = BBTI->getNumSuccessors(); i != e; ++i) 865dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (isa<PHINode>(BBTI->getSuccessor(i)->begin()) && 866dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner isCriticalEdge(BBTI, i, true)) 867dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner SplitEdgeNicely(BBTI, i, this); 868dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 869dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 870dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 871dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Keep track of non-local addresses that have been sunk into this block. 872dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This allows us to avoid inserting duplicate code for blocks with multiple 873dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // load/stores of the same address. 874dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DenseMap<Value*, Value*> SunkAddrs; 875dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 876dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (BasicBlock::iterator BBI = BB.begin(), E = BB.end(); BBI != E; ) { 877dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *I = BBI++; 878dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 879dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (CastInst *CI = dyn_cast<CastInst>(I)) { 880dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If the source of the cast is a constant, then this should have 881dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // already been constant folded. The only reason NOT to constant fold 882dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // it is if something (e.g. LSR) was careful to place the constant 883dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // evaluation in a block other than then one that uses it (e.g. to hoist 884dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // the address of globals out of a loop). If this is the case, we don't 885dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // want to forward-subst the cast. 886dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (isa<Constant>(CI->getOperand(0))) 887dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner continue; 888dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 889dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (TLI) 890dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner MadeChange |= OptimizeNoopCopyExpression(CI, *TLI); 891dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 892dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI) 893dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner MadeChange |= OptimizeLoadStoreInst(I, I->getOperand(0), LI->getType(), 894dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddrs); 895dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 896dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI) 897dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner MadeChange |= OptimizeLoadStoreInst(I, SI->getOperand(1), 898dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SI->getOperand(0)->getType(), 899dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddrs); 900dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 901f25646bfb375b614cddcc8b6fda2b524feae1efaChris Lattner if (GEPI->hasAllZeroIndices()) { 902dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner /// The GEP operand must be a pointer, so must its result -> BitCast 903dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 904dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->getName(), GEPI); 905dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->replaceAllUsesWith(NC); 906dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->eraseFromParent(); 907dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner MadeChange = true; 908dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner BBI = NC; 909dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 910dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (CallInst *CI = dyn_cast<CallInst>(I)) { 911dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If we found an inline asm expession, and if the target knows how to 912dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // lower it to normal LLVM code, do so now. 913dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI && isa<InlineAsm>(CI->getCalledValue())) 914dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (const TargetAsmInfo *TAI = 915dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner TLI->getTargetMachine().getTargetAsmInfo()) { 916dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TAI->ExpandInlineAsm(CI)) 917dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner BBI = BB.begin(); 918dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 919dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 920dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 921dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 922dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 923dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 924dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 925