CodeGenPrepare.cpp revision f5102a0f088e7c96f7028bf7ca1c24975c314fff
1dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner//===- CodeGenPrepare.cpp - Prepare a function for code generation --------===// 2dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// 3dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// The LLVM Compiler Infrastructure 4dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// 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 11a8a118b68fa3ca1632e7280cd6994aa0f8f1eec1Gordon Henriksen// SelectionDAG-based code generation. This works around limitations in it's 12a8a118b68fa3ca1632e7280cd6994aa0f8f1eec1Gordon Henriksen// 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" 219bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng#include "llvm/InlineAsm.h" 22dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Instructions.h" 23dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Pass.h" 24dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetAsmInfo.h" 25dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetData.h" 26dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetLowering.h" 27dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetMachine.h" 28dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 29dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Transforms/Utils/Local.h" 30dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/ADT/DenseMap.h" 31dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/ADT/SmallSet.h" 329bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng#include "llvm/Support/CallSite.h" 33d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner#include "llvm/Support/Compiler.h" 34bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng#include "llvm/Support/Debug.h" 35dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 36088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner#include "llvm/Support/PatternMatch.h" 37dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerusing namespace llvm; 38088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattnerusing namespace llvm::PatternMatch; 39dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 40692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christophernamespace { 41dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner class VISIBILITY_HIDDEN CodeGenPrepare : public FunctionPass { 42dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// TLI - Keep a pointer of a TargetLowering to consult for determining 43dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// transformation profitability. 44dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner const TargetLowering *TLI; 45dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner public: 46ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 47c2bbfc18e9adbbdcf5b3375d8d25e2452f7df7f1Dan Gohman explicit CodeGenPrepare(const TargetLowering *tli = 0) 48ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman : FunctionPass(&ID), TLI(tli) {} 49dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool runOnFunction(Function &F); 50692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 51dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner private: 52d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool EliminateMostlyEmptyBlocks(Function &F); 53d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; 54d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner void EliminateMostlyEmptyBlock(BasicBlock *BB); 55dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool OptimizeBlock(BasicBlock &BB); 5688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner bool OptimizeMemoryInst(Instruction *I, Value *Addr, const Type *AccessTy, 5788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner DenseMap<Value*,Value*> &SunkAddrs); 589bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng bool OptimizeInlineAsmInst(Instruction *I, CallSite CS, 599bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng DenseMap<Value*,Value*> &SunkAddrs); 60bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool OptimizeExtUses(Instruction *I); 61dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner }; 62dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 63794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 641997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar CodeGenPrepare::ID = 0; 65dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerstatic RegisterPass<CodeGenPrepare> X("codegenprepare", 66dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner "Optimize for code generation"); 67dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 68dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris LattnerFunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { 69dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return new CodeGenPrepare(TLI); 70dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 71dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 72dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 73dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::runOnFunction(Function &F) { 74dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool EverMadeChange = false; 75692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 76d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // First pass, eliminate blocks that contain only PHI nodes and an 77d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // unconditional branch. 78d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EverMadeChange |= EliminateMostlyEmptyBlocks(F); 79692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 80d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = true; 81dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner while (MadeChange) { 82dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = false; 83dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 84dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange |= OptimizeBlock(*BB); 85dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner EverMadeChange |= MadeChange; 86dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 87dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return EverMadeChange; 88dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 89dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 90d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes 91692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher/// and an unconditional branch. Passes before isel (e.g. LSR/loopsimplify) 92d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// often split edges in ways that are non-optimal for isel. Start by 93d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// eliminating these blocks so we can split them the way we want them. 94d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) { 95d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = false; 96d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Note that this intentionally skips the entry block. 97d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) { 98d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *BB = I++; 99d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 100d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If this block doesn't end with an uncond branch, ignore it. 101d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 102d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!BI || !BI->isUnconditional()) 103d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 104692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 105d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If the instruction before the branch isn't a phi node, then other stuff 106d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // is happening here. 107d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::iterator BBI = BI; 108d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBI != BB->begin()) { 109d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner --BBI; 110d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!isa<PHINode>(BBI)) continue; 111d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 112692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 113d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Do not break infinite loops. 114d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 115d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (DestBB == BB) 116d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 117692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 118d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!CanMergeBlocks(BB, DestBB)) 119d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 120692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 121d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EliminateMostlyEmptyBlock(BB); 122d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner MadeChange = true; 123d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 124d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return MadeChange; 125d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 126d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 127d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a 128d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// single uncond branch between them, and BB contains no other non-phi 129d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// instructions. 130d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, 131d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const BasicBlock *DestBB) const { 132d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // We only want to eliminate blocks whose phi nodes are used by phi nodes in 133d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // the successor. If there are more complex condition (e.g. preheaders), 134d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // don't mess around with them. 135d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::const_iterator BBI = BB->begin(); 136d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 137d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (Value::use_const_iterator UI = PN->use_begin(), E = PN->use_end(); 138d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner UI != E; ++UI) { 139d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Instruction *User = cast<Instruction>(*UI); 140d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (User->getParent() != DestBB || !isa<PHINode>(User)) 141d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return false; 142692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If User is inside DestBB block and it is a PHINode then check 143692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // incoming value. If incoming value is not from BB then this is 14475abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel // a complex condition (e.g. preheaders) we want to avoid here. 14575abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (User->getParent() == DestBB) { 14675abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (const PHINode *UPN = dyn_cast<PHINode>(User)) 14775abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { 14875abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); 14975abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (Insn && Insn->getParent() == BB && 15075abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Insn->getParent() != UPN->getIncomingBlock(I)) 15175abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel return false; 15275abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 15375abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 154d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 155d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 156692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 157d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If BB and DestBB contain any common predecessors, then the phi nodes in BB 158d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // and DestBB may have conflicting incoming values for the block. If so, we 159d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // can't merge the block. 160d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); 161d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!DestBBPN) return true; // no conflict. 162692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 163d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Collect the preds of BB. 164f67f73a519eac94b6c1f98dbce7d251a3a4aea07Chris Lattner SmallPtrSet<const BasicBlock*, 16> BBPreds; 165d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 166d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // It is faster to get preds from a PHI than with pred_iterator. 167d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 168d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(BBPN->getIncomingBlock(i)); 169d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 170d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(pred_begin(BB), pred_end(BB)); 171d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 172692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 173d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Walk the preds of DestBB. 174d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { 175d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *Pred = DestBBPN->getIncomingBlock(i); 176d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBPreds.count(Pred)) { // Common predecessor? 177d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBI = DestBB->begin(); 178d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 179d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V1 = PN->getIncomingValueForBlock(Pred); 180d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V2 = PN->getIncomingValueForBlock(BB); 181692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 182d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If V2 is a phi node in BB, look up what the mapped value will be. 183d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) 184d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V2PN->getParent() == BB) 185d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner V2 = V2PN->getIncomingValueForBlock(Pred); 186692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 187d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If there is a conflict, bail out. 188d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V1 != V2) return false; 189d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 190d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 191d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 192d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 193d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return true; 194d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 195d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 196d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 197d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and 198d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// an unconditional branch in it. 199d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnervoid CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { 200d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 201d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 202692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 203d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner DOUT << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB; 204692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 205d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If the destination block has a single pred, then this is a trivial edge, 206d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // just collapse it. 2079918fb5631974f2201a640384b7ebe672c749e43Chris Lattner if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) { 208f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (SinglePred != DestBB) { 209f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // Remember if SinglePred was the entry block of the function. If so, we 210f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // will need to move BB back to the entry position. 211f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 212f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner MergeBasicBlockIntoOnlyPred(DestBB); 213f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 214f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (isEntry && BB != &BB->getParent()->getEntryBlock()) 215f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner BB->moveBefore(&BB->getParent()->getEntryBlock()); 216f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 217f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner DOUT << "AFTER:\n" << *DestBB << "\n\n\n"; 218f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner return; 219f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner } 220d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 221692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 222d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB 223d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // to handle the new incoming edges it is about to have. 224d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *PN; 225d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (BasicBlock::iterator BBI = DestBB->begin(); 226d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 227d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Remove the incoming value for BB, and remember it. 228d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner Value *InVal = PN->removeIncomingValue(BB, false); 229692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 230d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Two options: either the InVal is a phi node defined in BB or it is some 231d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // value that dominates BB. 232d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *InValPhi = dyn_cast<PHINode>(InVal); 233d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (InValPhi && InValPhi->getParent() == BB) { 234d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Add all of the input values of the input PHI as inputs of this phi. 235d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) 236d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InValPhi->getIncomingValue(i), 237d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner InValPhi->getIncomingBlock(i)); 238d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 239d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, add one instance of the dominating value for each edge that 240d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // we will be adding. 241d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 242d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 243d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); 244d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 245d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 246d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, *PI); 247d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 248d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 249d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 250692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 251d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // The PHIs are now updated, change everything that refers to BB to use 252d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // DestBB and remove BB. 253d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->replaceAllUsesWith(DestBB); 254d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->eraseFromParent(); 255692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 256d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner DOUT << "AFTER:\n" << *DestBB << "\n\n\n"; 257d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 258d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 259d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 260ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner/// SplitEdgeNicely - Split the critical edge from TI to its specified 261dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// successor if it will improve codegen. We only do this if the successor has 262dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// phi nodes (otherwise critical edges are ok). If there is already another 263dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// predecessor of the succ that is empty (and thus has no phi nodes), use it 264dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// instead of introducing a new block. 265dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerstatic void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, Pass *P) { 266dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *TIBB = TI->getParent(); 267dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *Dest = TI->getSuccessor(SuccNum); 268dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner assert(isa<PHINode>(Dest->begin()) && 269dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner "This should only be called if Dest has a PHI!"); 270692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 271ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner // As a hack, never split backedges of loops. Even though the copy for any 272ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner // PHIs inserted on the backedge would be dead for exits from the loop, we 273ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner // assume that the cost of *splitting* the backedge would be too high. 274ff26ab227713afdd6f54f1b539df10cbe8f481e5Chris Lattner if (Dest == TIBB) 275ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner return; 276692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 277dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// TIPHIValues - This array is lazily computed to determine the values of 278dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// PHIs in Dest that TI would provide. 279ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner SmallVector<Value*, 32> TIPHIValues; 280692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 281dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Check to see if Dest has any blocks that can be used as a split edge for 282dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // this terminator. 283dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (pred_iterator PI = pred_begin(Dest), E = pred_end(Dest); PI != E; ++PI) { 284dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *Pred = *PI; 285dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // To be usable, the pred has to end with an uncond branch to the dest. 286dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator()); 287dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (!PredBr || !PredBr->isUnconditional() || 288dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Must be empty other than the branch. 2896603a1bff0e25e1d9f7be08c65c7b584c7bb84d7Dale Johannesen &Pred->front() != PredBr || 2906603a1bff0e25e1d9f7be08c65c7b584c7bb84d7Dale Johannesen // Cannot be the entry block; its label does not get emitted. 2916603a1bff0e25e1d9f7be08c65c7b584c7bb84d7Dale Johannesen Pred == &(Dest->getParent()->getEntryBlock())) 292dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner continue; 293692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 294dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Finally, since we know that Dest has phi nodes in it, we have to make 295dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // sure that jumping to Pred will have the same affect as going to Dest in 296dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // terms of PHI values. 297dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner PHINode *PN; 298dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner unsigned PHINo = 0; 299dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool FoundMatch = true; 300dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (BasicBlock::iterator I = Dest->begin(); 301dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) { 302dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (PHINo == TIPHIValues.size()) 303dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TIPHIValues.push_back(PN->getIncomingValueForBlock(TIBB)); 304692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 305dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If the PHI entry doesn't work, we can't use this pred. 306dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (TIPHIValues[PHINo] != PN->getIncomingValueForBlock(Pred)) { 307dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner FoundMatch = false; 308dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner break; 309dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 310dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 311692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 312dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we found a workable predecessor, change TI to branch to Succ. 313dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (FoundMatch) { 314dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Dest->removePredecessor(TIBB); 315dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TI->setSuccessor(SuccNum, Pred); 316dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return; 317dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 318dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 319692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 320692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher SplitCriticalEdge(TI, SuccNum, P, true); 321dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 322dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 323dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// OptimizeNoopCopyExpression - If the specified cast instruction is a noop 324dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// copy (e.g. it's casting from one pointer type to another, int->uint, or 325dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// int->sbyte on PPC), sink it into user blocks to reduce the number of virtual 326ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// registers that must be created and coalesced. 327dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// 328dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// Return true if any changes are made. 32985fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner/// 330dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){ 331692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If this is a noop copy, 33283ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands MVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 33383ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands MVT DstVT = TLI.getValueType(CI->getType()); 334692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 335dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This is an fp<->int conversion? 33683ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands if (SrcVT.isInteger() != DstVT.isInteger()) 337dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 3388e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands 339dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is an extension, it will be a zero or sign extension, which 340dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // isn't a noop. 3418e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands if (SrcVT.bitsLT(DstVT)) return false; 342692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 343dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If these values will be promoted, find out what they will be promoted 344dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // to. This helps us consider truncates on PPC as noop copies when they 345dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // are. 346dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) 347dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SrcVT = TLI.getTypeToTransformTo(SrcVT); 348dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.getTypeAction(DstVT) == TargetLowering::Promote) 349dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DstVT = TLI.getTypeToTransformTo(DstVT); 350692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 351dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If, after promotion, these are the same types, this is a noop copy. 352dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SrcVT != DstVT) 353dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 354692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 355dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *DefBB = CI->getParent(); 356692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 357dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// InsertedCasts - Only insert a cast in each block once. 358ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CastInst*> InsertedCasts; 359692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 360dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 361692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 362dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner UI != E; ) { 363dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Use &TheUse = UI.getUse(); 364dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *User = cast<Instruction>(*UI); 365692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 366dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Figure out which BB this cast is used in. For PHI's this is the 367dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // appropriate predecessor block. 368dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *UserBB = User->getParent(); 369dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) { 370dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner unsigned OpVal = UI.getOperandNo()/2; 371dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner UserBB = PN->getIncomingBlock(OpVal); 372dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 373692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 374dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Preincrement use iterator so we don't invalidate it. 375dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner ++UI; 376692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 377dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If this user is in the same block as the cast, don't change the cast. 378dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (UserBB == DefBB) continue; 379692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 380dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we have already inserted a cast into this block, use it. 381dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CastInst *&InsertedCast = InsertedCasts[UserBB]; 382dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 383dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (!InsertedCast) { 38402dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 385692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 386692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCast = 387692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 388dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner InsertPt); 389dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = true; 390dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 391692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 392ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cast with a use of the new cast. 393dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TheUse = InsertedCast; 394dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 395692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 396dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we removed all uses, nuke the cast. 397e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands if (CI->use_empty()) { 398dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CI->eraseFromParent(); 399e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands MadeChange = true; 400e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands } 401692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 402dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 403dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 404dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 405692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher/// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce 406ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// the number of virtual registers that must be created and coalesced. This is 407684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// a clear win except on targets with multiple condition code registers 408684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// (PowerPC), where it might lose; some adjustment may be wanted there. 409ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// 410ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// Return true if any changes are made. 41185fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattnerstatic bool OptimizeCmpExpression(CmpInst *CI) { 412ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *DefBB = CI->getParent(); 413692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 414ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen /// InsertedCmp - Only insert a cmp in each block once. 415ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CmpInst*> InsertedCmps; 416692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 417ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen bool MadeChange = false; 418692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 419ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen UI != E; ) { 420ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Use &TheUse = UI.getUse(); 421ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Instruction *User = cast<Instruction>(*UI); 422692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 423ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Preincrement use iterator so we don't invalidate it. 424ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen ++UI; 425692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 426ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Don't bother for PHI nodes. 427ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (isa<PHINode>(User)) 428ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen continue; 429ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 430ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Figure out which BB this cmp is used in. 431ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *UserBB = User->getParent(); 432692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 433ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If this user is in the same block as the cmp, don't change the cmp. 434ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (UserBB == DefBB) continue; 435692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 436ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we have already inserted a cmp into this block, use it. 437ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CmpInst *&InsertedCmp = InsertedCmps[UserBB]; 438ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 439ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (!InsertedCmp) { 44002dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 441692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 442692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCmp = 443692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher CmpInst::Create(CI->getOpcode(), CI->getPredicate(), CI->getOperand(0), 444ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->getOperand(1), "", InsertPt); 445ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen MadeChange = true; 446ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 447692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 448ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cmp with a use of the new cmp. 449ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen TheUse = InsertedCmp; 450ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 451692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 452ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we removed all uses, nuke the cmp. 453ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (CI->use_empty()) 454ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->eraseFromParent(); 455692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 456ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen return MadeChange; 457ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen} 458ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 45988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 46088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner// Addressing Mode Analysis and Optimization 46188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 46288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 463844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 4644744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner /// ExtAddrMode - This is an extended version of TargetLowering::AddrMode 4654744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner /// which holds actual Value*'s for register values. 4664744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner struct ExtAddrMode : public TargetLowering::AddrMode { 4674744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner Value *BaseReg; 4684744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner Value *ScaledReg; 4694744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner ExtAddrMode() : BaseReg(0), ScaledReg(0) {} 4704744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner void print(OStream &OS) const; 4714744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner void dump() const { 4724744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner print(cerr); 4734744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner cerr << '\n'; 4744744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner } 4754744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner }; 4764744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner} // end anonymous namespace 4774744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner 4785eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattnerstatic inline OStream &operator<<(OStream &OS, const ExtAddrMode &AM) { 4794744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner AM.print(OS); 4804744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner return OS; 4814744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner} 482dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 4834744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattnervoid ExtAddrMode::print(OStream &OS) const { 484dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool NeedPlus = false; 485dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner OS << "["; 4864744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner if (BaseGV) 487dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner OS << (NeedPlus ? " + " : "") 4884744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner << "GV:%" << BaseGV->getName(), NeedPlus = true; 489692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 4904744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner if (BaseOffs) 4914744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner OS << (NeedPlus ? " + " : "") << BaseOffs, NeedPlus = true; 492692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 4934744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner if (BaseReg) 494dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner OS << (NeedPlus ? " + " : "") 4954744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner << "Base:%" << BaseReg->getName(), NeedPlus = true; 4964744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner if (Scale) 497dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner OS << (NeedPlus ? " + " : "") 4984744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner << Scale << "*%" << ScaledReg->getName(), NeedPlus = true; 499dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 5004744d85c50363ad60fe1767877fb0875e09c6b11Chris Lattner OS << ']'; 501844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} 502844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 50388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattnernamespace { 50488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// AddressingModeMatcher - This class exposes a single public method, which is 50588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// used to construct a "maximal munch" of the addressing mode for the target 50688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// specified by TLI for an access to "V" with an access type of AccessTy. This 50788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// returns the addressing mode that is actually matched by value, but also 50888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// returns the list of instructions involved in that addressing computation in 50988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// AddrModeInsts. 51088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattnerclass AddressingModeMatcher { 51188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner SmallVectorImpl<Instruction*> &AddrModeInsts; 51288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner const TargetLowering &TLI; 513896617b776e7b015346160645b19be776cbe3805Chris Lattner 514896617b776e7b015346160645b19be776cbe3805Chris Lattner /// AccessTy/MemoryInst - This is the type for the access (e.g. double) and 515896617b776e7b015346160645b19be776cbe3805Chris Lattner /// the memory instruction that we're computing this address for. 51688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner const Type *AccessTy; 517896617b776e7b015346160645b19be776cbe3805Chris Lattner Instruction *MemoryInst; 518896617b776e7b015346160645b19be776cbe3805Chris Lattner 519896617b776e7b015346160645b19be776cbe3805Chris Lattner /// AddrMode - This is the addressing mode that we're building up. This is 520896617b776e7b015346160645b19be776cbe3805Chris Lattner /// part of the return value of this addressing mode matching stuff. 52188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner ExtAddrMode &AddrMode; 5225eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 5235eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner /// IgnoreProfitability - This is set to true when we should not do 5245eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner /// profitability checks. When true, IsProfitableToFoldIntoAddressingMode 5255eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner /// always returns true. 5265eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner bool IgnoreProfitability; 5275eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 52888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner AddressingModeMatcher(SmallVectorImpl<Instruction*> &AMI, 529896617b776e7b015346160645b19be776cbe3805Chris Lattner const TargetLowering &T, const Type *AT, 530896617b776e7b015346160645b19be776cbe3805Chris Lattner Instruction *MI, ExtAddrMode &AM) 531896617b776e7b015346160645b19be776cbe3805Chris Lattner : AddrModeInsts(AMI), TLI(T), AccessTy(AT), MemoryInst(MI), AddrMode(AM) { 5325eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner IgnoreProfitability = false; 5335eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner } 53488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattnerpublic: 53588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 5365eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner /// Match - Find the maximal addressing mode that a load/store of V can fold, 5375eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner /// give an access type of AccessTy. This returns a list of involved 5385eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner /// instructions in AddrModeInsts. 539896617b776e7b015346160645b19be776cbe3805Chris Lattner static ExtAddrMode Match(Value *V, const Type *AccessTy, 540896617b776e7b015346160645b19be776cbe3805Chris Lattner Instruction *MemoryInst, 54188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner SmallVectorImpl<Instruction*> &AddrModeInsts, 54288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner const TargetLowering &TLI) { 54388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner ExtAddrMode Result; 54488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 54588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner bool Success = 546896617b776e7b015346160645b19be776cbe3805Chris Lattner AddressingModeMatcher(AddrModeInsts, TLI, AccessTy, 547896617b776e7b015346160645b19be776cbe3805Chris Lattner MemoryInst, Result).MatchAddr(V, 0); 54888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner Success = Success; assert(Success && "Couldn't select *anything*?"); 54988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner return Result; 55088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner } 55188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattnerprivate: 5523b48501adc540c834fe33bf2695377c7e1189d3cChris Lattner bool MatchScaledValue(Value *ScaleReg, int64_t Scale, unsigned Depth); 55388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner bool MatchAddr(Value *V, unsigned Depth); 55488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner bool MatchOperationAddr(User *Operation, unsigned Opcode, unsigned Depth); 55584d1b40d448663050f12fb4dee052db907ac4748Chris Lattner bool IsProfitableToFoldIntoAddressingMode(Instruction *I, 55684d1b40d448663050f12fb4dee052db907ac4748Chris Lattner ExtAddrMode &AMBefore, 55784d1b40d448663050f12fb4dee052db907ac4748Chris Lattner ExtAddrMode &AMAfter); 55884d1b40d448663050f12fb4dee052db907ac4748Chris Lattner bool ValueAlreadyLiveAtInst(Value *Val, Value *KnownLive1, Value *KnownLive2); 55988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner}; 56088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner} // end anonymous namespace 56188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 56288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// MatchScaledValue - Try adding ScaleReg*Scale to the current addressing mode. 56388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// Return true and update AddrMode if this addr mode is legal for the target, 56485fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner/// false if not. 5653b48501adc540c834fe33bf2695377c7e1189d3cChris Lattnerbool AddressingModeMatcher::MatchScaledValue(Value *ScaleReg, int64_t Scale, 5663b48501adc540c834fe33bf2695377c7e1189d3cChris Lattner unsigned Depth) { 5673b48501adc540c834fe33bf2695377c7e1189d3cChris Lattner // If Scale is 1, then this is the same as adding ScaleReg to the addressing 5683b48501adc540c834fe33bf2695377c7e1189d3cChris Lattner // mode. Just process that directly. 5693b48501adc540c834fe33bf2695377c7e1189d3cChris Lattner if (Scale == 1) 5703b48501adc540c834fe33bf2695377c7e1189d3cChris Lattner return MatchAddr(ScaleReg, Depth); 5713b48501adc540c834fe33bf2695377c7e1189d3cChris Lattner 5723b48501adc540c834fe33bf2695377c7e1189d3cChris Lattner // If the scale is 0, it takes nothing to add this. 5733b48501adc540c834fe33bf2695377c7e1189d3cChris Lattner if (Scale == 0) 5743b48501adc540c834fe33bf2695377c7e1189d3cChris Lattner return true; 5753b48501adc540c834fe33bf2695377c7e1189d3cChris Lattner 57685fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner // If we already have a scale of this value, we can add to it, otherwise, we 57785fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner // need an available scale field. 57885fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg) 57985fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner return false; 58085fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner 581088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner ExtAddrMode TestAddrMode = AddrMode; 58285fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner 58385fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner // Add scale to turn X*4+X*3 -> X*7. This could also do things like 58485fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner // [A+B + A*7] -> [B+A*8]. 585088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner TestAddrMode.Scale += Scale; 586088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner TestAddrMode.ScaledReg = ScaleReg; 58785fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner 588088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner // If the new address isn't legal, bail out. 589088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner if (!TLI.isLegalAddressingMode(TestAddrMode, AccessTy)) 590088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner return false; 59185fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner 592088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner // It was legal, so commit it. 593088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner AddrMode = TestAddrMode; 594088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner 595088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner // Okay, we decided that we can add ScaleReg+Scale to AddrMode. Check now 596088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner // to see if ScaleReg is actually X+C. If so, we can turn this into adding 597088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner // X*Scale + C*Scale to addr mode. 598088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner ConstantInt *CI; Value *AddLHS; 599088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner if (match(ScaleReg, m_Add(m_Value(AddLHS), m_ConstantInt(CI)))) { 600088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner TestAddrMode.ScaledReg = AddLHS; 601088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner TestAddrMode.BaseOffs += CI->getSExtValue()*TestAddrMode.Scale; 602088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner 603088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner // If this addressing mode is legal, commit it and remember that we folded 604088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner // this instruction. 605088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner if (TLI.isLegalAddressingMode(TestAddrMode, AccessTy)) { 606088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner AddrModeInsts.push_back(cast<Instruction>(ScaleReg)); 607088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner AddrMode = TestAddrMode; 60888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner return true; 609088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner } 610088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner } 61185fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner 612088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner // Otherwise, not (x+c)*scale, just return what we have. 613088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner return true; 61485fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner} 61585fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner 6165eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// MightBeFoldableInst - This is a little filter, which returns true if an 6175eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// addressing computation involving I might be folded into a load/store 6185eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// accessing it. This doesn't need to be perfect, but needs to accept at least 6195eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// the set of instructions that MatchOperationAddr can. 6205eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattnerstatic bool MightBeFoldableInst(Instruction *I) { 6215eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner switch (I->getOpcode()) { 6225eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner case Instruction::BitCast: 6235eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // Don't touch identity bitcasts. 6245eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner if (I->getType() == I->getOperand(0)->getType()) 6255eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return false; 6265eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return isa<PointerType>(I->getType()) || isa<IntegerType>(I->getType()); 6275eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner case Instruction::PtrToInt: 6285eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // PtrToInt is always a noop, as we know that the int type is pointer sized. 6295eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return true; 6305eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner case Instruction::IntToPtr: 6315eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // We know the input is intptr_t, so this is foldable. 6325eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return true; 6335eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner case Instruction::Add: 6345eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return true; 6355eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner case Instruction::Mul: 6365eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner case Instruction::Shl: 6375eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // Can only handle X*C and X << C. 6385eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return isa<ConstantInt>(I->getOperand(1)); 6395eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner case Instruction::GetElementPtr: 6405eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return true; 6415eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner default: 6425eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return false; 6435eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner } 6445eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner} 6455eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 64688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 64788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// MatchOperationAddr - Given an instruction or constant expr, see if we can 64888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// fold the operation into the addressing mode. If so, update the addressing 64988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// mode and return true, otherwise return false without modifying AddrMode. 65088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattnerbool AddressingModeMatcher::MatchOperationAddr(User *AddrInst, unsigned Opcode, 65188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner unsigned Depth) { 65288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner // Avoid exponential behavior on extremely deep expression trees. 65388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner if (Depth >= 5) return false; 65488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 655dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner switch (Opcode) { 656dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::PtrToInt: 657dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // PtrToInt is always a noop, as we know that the int type is pointer sized. 65888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner return MatchAddr(AddrInst->getOperand(0), Depth); 659dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::IntToPtr: 660dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This inttoptr is a no-op if the integer type is pointer sized. 661dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.getValueType(AddrInst->getOperand(0)->getType()) == 66288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner TLI.getPointerTy()) 66388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner return MatchAddr(AddrInst->getOperand(0), Depth); 6642efbbb38ba7b9601202f2271301f07195dea8959Chris Lattner return false; 6652efbbb38ba7b9601202f2271301f07195dea8959Chris Lattner case Instruction::BitCast: 6662efbbb38ba7b9601202f2271301f07195dea8959Chris Lattner // BitCast is always a noop, and we can handle it as long as it is 6672efbbb38ba7b9601202f2271301f07195dea8959Chris Lattner // int->int or pointer->pointer (we don't want int<->fp or something). 6682efbbb38ba7b9601202f2271301f07195dea8959Chris Lattner if ((isa<PointerType>(AddrInst->getOperand(0)->getType()) || 6692efbbb38ba7b9601202f2271301f07195dea8959Chris Lattner isa<IntegerType>(AddrInst->getOperand(0)->getType())) && 6702efbbb38ba7b9601202f2271301f07195dea8959Chris Lattner // Don't touch identity bitcasts. These were probably put here by LSR, 6712efbbb38ba7b9601202f2271301f07195dea8959Chris Lattner // and we don't want to mess around with them. Assume it knows what it 6722efbbb38ba7b9601202f2271301f07195dea8959Chris Lattner // is doing. 6732efbbb38ba7b9601202f2271301f07195dea8959Chris Lattner AddrInst->getOperand(0)->getType() != AddrInst->getType()) 6742efbbb38ba7b9601202f2271301f07195dea8959Chris Lattner return MatchAddr(AddrInst->getOperand(0), Depth); 67588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner return false; 676dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::Add: { 677dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if we can merge in the RHS then the LHS. If so, we win. 678dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ExtAddrMode BackupAddrMode = AddrMode; 679dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner unsigned OldSize = AddrModeInsts.size(); 68088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner if (MatchAddr(AddrInst->getOperand(1), Depth+1) && 68188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner MatchAddr(AddrInst->getOperand(0), Depth+1)) 682dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 683bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner 684dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Restore the old addr mode info. 685dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode = BackupAddrMode; 686dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts.resize(OldSize); 687bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner 688dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Otherwise this was over-aggressive. Try merging in the LHS then the RHS. 68988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner if (MatchAddr(AddrInst->getOperand(0), Depth+1) && 69088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner MatchAddr(AddrInst->getOperand(1), Depth+1)) 691dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 692bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner 693dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Otherwise we definitely can't merge the ADD in. 694dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode = BackupAddrMode; 695dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts.resize(OldSize); 696692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher break; 697dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 6985eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner //case Instruction::Or: 6995eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD. 7005eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner //break; 701dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::Mul: 702dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::Shl: { 7037ad1c7342bb6619ebf13284377e2b479830d096fChris Lattner // Can only handle X*C and X << C. 704dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1)); 70588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner if (!RHS) return false; 706dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner int64_t Scale = RHS->getSExtValue(); 707dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Opcode == Instruction::Shl) 708dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Scale = 1 << Scale; 709bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner 7103b48501adc540c834fe33bf2695377c7e1189d3cChris Lattner return MatchScaledValue(AddrInst->getOperand(0), Scale, Depth); 711dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 712dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::GetElementPtr: { 713dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Scan the GEP. We check it if it contains constant offsets and at most 714dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // one variable offset. 715dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner int VariableOperand = -1; 716dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner unsigned VariableScale = 0; 717bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner 718dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner int64_t ConstantOffset = 0; 719dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const TargetData *TD = TLI.getTargetData(); 720dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner gep_type_iterator GTI = gep_type_begin(AddrInst); 721dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) { 722dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (const StructType *STy = dyn_cast<StructType>(*GTI)) { 723dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const StructLayout *SL = TD->getStructLayout(STy); 724dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner unsigned Idx = 72588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue(); 726dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ConstantOffset += SL->getElementOffset(Idx); 727dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 728514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands uint64_t TypeSize = TD->getABITypeSize(GTI.getIndexedType()); 729dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(AddrInst->getOperand(i))) { 730dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ConstantOffset += CI->getSExtValue()*TypeSize; 731dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (TypeSize) { // Scales of zero don't do anything. 732dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // We only allow one variable index at the moment. 73388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner if (VariableOperand != -1) 73488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner return false; 735bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner 736dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Remember the variable index. 737dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner VariableOperand = i; 738dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner VariableScale = TypeSize; 739dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 740dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 741dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 742bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner 743dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // A common case is for the GEP to only do a constant offset. In this case, 744dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // just add it to the disp field and check validity. 745dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (VariableOperand == -1) { 746dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseOffs += ConstantOffset; 747dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (ConstantOffset == 0 || TLI.isLegalAddressingMode(AddrMode, AccessTy)){ 748dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if we can fold the base pointer in too. 74988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner if (MatchAddr(AddrInst->getOperand(0), Depth+1)) 750dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 751dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 752dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseOffs -= ConstantOffset; 75388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner return false; 754dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 75588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 75688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner // Save the valid addressing mode in case we can't match. 75788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner ExtAddrMode BackupAddrMode = AddrMode; 75888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 75988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner // Check that this has no base reg yet. If so, we won't have a place to 76088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner // put the base of the GEP (assuming it is not a null ptr). 76188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner bool SetBaseReg = true; 76288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner if (isa<ConstantPointerNull>(AddrInst->getOperand(0))) 76388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner SetBaseReg = false; // null pointer base doesn't need representation. 76488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner else if (AddrMode.HasBaseReg) 76588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner return false; // Base register already specified, can't match GEP. 76688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner else { 76788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner // Otherwise, we'll use the GEP base as the BaseReg. 76888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner AddrMode.HasBaseReg = true; 76988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner AddrMode.BaseReg = AddrInst->getOperand(0); 77088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner } 77188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 77288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner // See if the scale and offset amount is valid for this target. 77388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner AddrMode.BaseOffs += ConstantOffset; 77488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 7753b48501adc540c834fe33bf2695377c7e1189d3cChris Lattner if (!MatchScaledValue(AddrInst->getOperand(VariableOperand), VariableScale, 7763b48501adc540c834fe33bf2695377c7e1189d3cChris Lattner Depth)) { 77788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner AddrMode = BackupAddrMode; 77888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner return false; 77988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner } 78088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 78188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner // If we have a null as the base of the GEP, folding in the constant offset 78288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner // plus variable scale is all we can do. 78388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner if (!SetBaseReg) return true; 78488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 78588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner // If this match succeeded, we know that we can form an address with the 78688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner // GepBase as the basereg. Match the base pointer of the GEP more 78788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner // aggressively by zeroing out BaseReg and rematching. If the base is 78888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner // (for example) another GEP, this allows merging in that other GEP into 78988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner // the addressing mode we're forming. 79088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner AddrMode.HasBaseReg = false; 79188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner AddrMode.BaseReg = 0; 79288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner bool Success = MatchAddr(AddrInst->getOperand(0), Depth+1); 79388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner assert(Success && "MatchAddr should be able to fill in BaseReg!"); 79488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner Success=Success; 79588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner return true; 796dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 797dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 798bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner return false; 799bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner} 800692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 80188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// MatchAddr - If we can, try to add the value of 'Addr' into the current 80288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// addressing mode. If Addr can't be added to AddrMode this returns false and 80388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// leaves AddrMode unmodified. This assumes that Addr is either a pointer type 80488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// or intptr_t for the target. 805bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner/// 80688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattnerbool AddressingModeMatcher::MatchAddr(Value *Addr, unsigned Depth) { 807bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(Addr)) { 808bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner // Fold in immediates if legal for the target. 809bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner AddrMode.BaseOffs += CI->getSExtValue(); 810bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 811bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner return true; 812bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner AddrMode.BaseOffs -= CI->getSExtValue(); 813bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner } else if (GlobalValue *GV = dyn_cast<GlobalValue>(Addr)) { 81488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner // If this is a global variable, try to fold it into the addressing mode. 815bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner if (AddrMode.BaseGV == 0) { 816bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner AddrMode.BaseGV = GV; 817bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 818bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner return true; 819bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner AddrMode.BaseGV = 0; 820bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner } 821bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner } else if (Instruction *I = dyn_cast<Instruction>(Addr)) { 8225eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner ExtAddrMode BackupAddrMode = AddrMode; 8235eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner unsigned OldSize = AddrModeInsts.size(); 8245eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 8255eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // Check to see if it is possible to fold this operation. 82688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner if (MatchOperationAddr(I, I->getOpcode(), Depth)) { 8275eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // Okay, it's possible to fold this. Check to see if it is actually 8285eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // *profitable* to do so. We use a simple cost model to avoid increasing 8295eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // register pressure too much. 83084d1b40d448663050f12fb4dee052db907ac4748Chris Lattner if (I->hasOneUse() || 83184d1b40d448663050f12fb4dee052db907ac4748Chris Lattner IsProfitableToFoldIntoAddressingMode(I, BackupAddrMode, AddrMode)) { 8325eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner AddrModeInsts.push_back(I); 8335eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return true; 8345eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner } 8355eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 8365eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // It isn't profitable to do this, roll back. 8375eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner //cerr << "NOT FOLDING: " << *I; 8385eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner AddrMode = BackupAddrMode; 8395eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner AddrModeInsts.resize(OldSize); 840bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner } 841bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) { 84288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner if (MatchOperationAddr(CE, CE->getOpcode(), Depth)) 843bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner return true; 844bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner } else if (isa<ConstantPointerNull>(Addr)) { 84588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner // Null pointer gets folded without affecting the addressing mode. 846bb3204a440e3cf5f9bd44f05d34f99b7450341e6Chris Lattner return true; 847dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 848692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 849dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Worse case, the target should support [reg] addressing modes. :) 850dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!AddrMode.HasBaseReg) { 851dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.HasBaseReg = true; 852653b2581df384f5442ef2438b11864576e6b549bChris Lattner AddrMode.BaseReg = Addr; 853dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Still check for legality in case the target supports [imm] but not [i+r]. 854653b2581df384f5442ef2438b11864576e6b549bChris Lattner if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 855dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 856dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.HasBaseReg = false; 857653b2581df384f5442ef2438b11864576e6b549bChris Lattner AddrMode.BaseReg = 0; 858dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 859692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 860dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If the base register is already taken, see if we can do [r+r]. 861dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale == 0) { 862dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.Scale = 1; 863653b2581df384f5442ef2438b11864576e6b549bChris Lattner AddrMode.ScaledReg = Addr; 864653b2581df384f5442ef2438b11864576e6b549bChris Lattner if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 865dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 866dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.Scale = 0; 867653b2581df384f5442ef2438b11864576e6b549bChris Lattner AddrMode.ScaledReg = 0; 868dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 869dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Couldn't match. 870dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 871dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 872dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 873695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner 874695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner/// IsOperandAMemoryOperand - Check to see if all uses of OpVal by the specified 875695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner/// inline asm call are due to memory operands. If so, return true, otherwise 876695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner/// return false. 877695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattnerstatic bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal, 878695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner const TargetLowering &TLI) { 879695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner std::vector<InlineAsm::ConstraintInfo> 880695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner Constraints = IA->ParseConstraints(); 881695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner 882695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner unsigned ArgNo = 1; // ArgNo - The operand of the CallInst. 883695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { 884695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner TargetLowering::AsmOperandInfo OpInfo(Constraints[i]); 885695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner 886695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner // Compute the value type for each operand. 887695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner switch (OpInfo.Type) { 888695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner case InlineAsm::isOutput: 889695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner if (OpInfo.isIndirect) 890695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner OpInfo.CallOperandVal = CI->getOperand(ArgNo++); 891695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner break; 892695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner case InlineAsm::isInput: 893695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner OpInfo.CallOperandVal = CI->getOperand(ArgNo++); 894695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner break; 895695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner case InlineAsm::isClobber: 896695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner // Nothing to do. 897695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner break; 898695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner } 899695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner 900695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner // Compute the constraint code and ConstraintType to use. 901695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner TLI.ComputeConstraintToUse(OpInfo, SDValue(), 902695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner OpInfo.ConstraintType == TargetLowering::C_Memory); 903695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner 904695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner // If this asm operand is our Value*, and if it isn't an indirect memory 905695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner // operand, we can't fold it! 906695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner if (OpInfo.CallOperandVal == OpVal && 907695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner (OpInfo.ConstraintType != TargetLowering::C_Memory || 908695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner !OpInfo.isIndirect)) 909695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner return false; 910695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner } 911695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner 912695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner return true; 913695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner} 914695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner 915695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner 9165eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// FindAllMemoryUses - Recursively walk all the uses of I until we find a 9175eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// memory use. If we find an obviously non-foldable instruction, return true. 9185eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// Add the ultimately found memory instructions to MemoryUses. 9195eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattnerstatic bool FindAllMemoryUses(Instruction *I, 9205eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner SmallVectorImpl<std::pair<Instruction*,unsigned> > &MemoryUses, 921695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner SmallPtrSet<Instruction*, 16> &ConsideredInsts, 922695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner const TargetLowering &TLI) { 9235eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // If we already considered this instruction, we're done. 9245eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner if (!ConsideredInsts.insert(I)) 9255eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return false; 9265eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 9275eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // If this is an obviously unfoldable instruction, bail out. 9285eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner if (!MightBeFoldableInst(I)) 9295eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return true; 9305eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 9315eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // Loop over all the uses, recursively processing them. 9325eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 9335eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner UI != E; ++UI) { 9345eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 9355eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner MemoryUses.push_back(std::make_pair(LI, UI.getOperandNo())); 9365eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner continue; 9375eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner } 9385eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 9395eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 9405eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner if (UI.getOperandNo() == 0) return true; // Storing addr, not into addr. 9415eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner MemoryUses.push_back(std::make_pair(SI, UI.getOperandNo())); 9425eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner continue; 9435eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner } 9445eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 9455eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner if (CallInst *CI = dyn_cast<CallInst>(*UI)) { 9465eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue()); 9475eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner if (IA == 0) return true; 9485eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 949695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner // If this is a memory operand, we're cool, otherwise bail out. 950695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner if (!IsOperandAMemoryOperand(CI, IA, I, TLI)) 951695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner return true; 952695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner continue; 9535eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner } 9545eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 955695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner if (FindAllMemoryUses(cast<Instruction>(*UI), MemoryUses, ConsideredInsts, 956695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner TLI)) 9575eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return true; 9585eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner } 9595eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 9605eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return false; 9615eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner} 96284d1b40d448663050f12fb4dee052db907ac4748Chris Lattner 96384d1b40d448663050f12fb4dee052db907ac4748Chris Lattner 96484d1b40d448663050f12fb4dee052db907ac4748Chris Lattner/// ValueAlreadyLiveAtInst - Retrn true if Val is already known to be live at 96584d1b40d448663050f12fb4dee052db907ac4748Chris Lattner/// the use site that we're folding it into. If so, there is no cost to 96684d1b40d448663050f12fb4dee052db907ac4748Chris Lattner/// include it in the addressing mode. KnownLive1 and KnownLive2 are two values 96784d1b40d448663050f12fb4dee052db907ac4748Chris Lattner/// that we know are live at the instruction already. 96884d1b40d448663050f12fb4dee052db907ac4748Chris Lattnerbool AddressingModeMatcher::ValueAlreadyLiveAtInst(Value *Val,Value *KnownLive1, 96984d1b40d448663050f12fb4dee052db907ac4748Chris Lattner Value *KnownLive2) { 97084d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // If Val is either of the known-live values, we know it is live! 97184d1b40d448663050f12fb4dee052db907ac4748Chris Lattner if (Val == 0 || Val == KnownLive1 || Val == KnownLive2) 97284d1b40d448663050f12fb4dee052db907ac4748Chris Lattner return true; 97384d1b40d448663050f12fb4dee052db907ac4748Chris Lattner 974896617b776e7b015346160645b19be776cbe3805Chris Lattner // All values other than instructions and arguments (e.g. constants) are live. 97584d1b40d448663050f12fb4dee052db907ac4748Chris Lattner if (!isa<Instruction>(Val) && !isa<Argument>(Val)) return true; 9765eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 97784d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // If Val is a constant sized alloca in the entry block, it is live, this is 97884d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // true because it is just a reference to the stack/frame pointer, which is 97984d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // live for the whole function. 98084d1b40d448663050f12fb4dee052db907ac4748Chris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(Val)) 98184d1b40d448663050f12fb4dee052db907ac4748Chris Lattner if (AI->isStaticAlloca()) 98284d1b40d448663050f12fb4dee052db907ac4748Chris Lattner return true; 98384d1b40d448663050f12fb4dee052db907ac4748Chris Lattner 984896617b776e7b015346160645b19be776cbe3805Chris Lattner // Check to see if this value is already used in the memory instruction's 985896617b776e7b015346160645b19be776cbe3805Chris Lattner // block. If so, it's already live into the block at the very least, so we 986896617b776e7b015346160645b19be776cbe3805Chris Lattner // can reasonably fold it. 987896617b776e7b015346160645b19be776cbe3805Chris Lattner BasicBlock *MemBB = MemoryInst->getParent(); 988896617b776e7b015346160645b19be776cbe3805Chris Lattner for (Value::use_iterator UI = Val->use_begin(), E = Val->use_end(); 989896617b776e7b015346160645b19be776cbe3805Chris Lattner UI != E; ++UI) 990896617b776e7b015346160645b19be776cbe3805Chris Lattner // We know that uses of arguments and instructions have to be instructions. 991896617b776e7b015346160645b19be776cbe3805Chris Lattner if (cast<Instruction>(*UI)->getParent() == MemBB) 992896617b776e7b015346160645b19be776cbe3805Chris Lattner return true; 993896617b776e7b015346160645b19be776cbe3805Chris Lattner 99484d1b40d448663050f12fb4dee052db907ac4748Chris Lattner return false; 99584d1b40d448663050f12fb4dee052db907ac4748Chris Lattner} 99684d1b40d448663050f12fb4dee052db907ac4748Chris Lattner 99784d1b40d448663050f12fb4dee052db907ac4748Chris Lattner 99884d1b40d448663050f12fb4dee052db907ac4748Chris Lattner 9995eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// IsProfitableToFoldIntoAddressingMode - It is possible for the addressing 10005eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// mode of the machine to fold the specified instruction into a load or store 10015eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// that ultimately uses it. However, the specified instruction has multiple 10025eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// uses. Given this, it may actually increase register pressure to fold it 10035eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// into the load. For example, consider this code: 10045eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// 10055eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// X = ... 10065eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// Y = X+1 10075eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// use(Y) -> nonload/store 10085eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// Z = Y+1 10095eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// load Z 10105eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// 10115eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// In this case, Y has multiple uses, and can be folded into the load of Z 10125eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// (yielding load [X+2]). However, doing this will cause both "X" and "X+1" to 10135eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// be live at the use(Y) line. If we don't fold Y into load Z, we use one 10145eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// fewer register. Since Y can't be folded into "use(Y)" we don't increase the 10155eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// number of computations either. 10165eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// 10175eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// Note that this (like most of CodeGenPrepare) is just a rough heuristic. If 10185eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner/// X was live across 'load Z' for other reasons, we actually *would* want to 1019653b2581df384f5442ef2438b11864576e6b549bChris Lattner/// fold the addressing mode in the Z case. This would make Y die earlier. 10205eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattnerbool AddressingModeMatcher:: 102184d1b40d448663050f12fb4dee052db907ac4748Chris LattnerIsProfitableToFoldIntoAddressingMode(Instruction *I, ExtAddrMode &AMBefore, 102284d1b40d448663050f12fb4dee052db907ac4748Chris Lattner ExtAddrMode &AMAfter) { 1023ab8b794a789390ca2f1ad5372d4813911e306663Chris Lattner if (IgnoreProfitability) return true; 10245eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 102584d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // AMBefore is the addressing mode before this instruction was folded into it, 102684d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // and AMAfter is the addressing mode after the instruction was folded. Get 102784d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // the set of registers referenced by AMAfter and subtract out those 102884d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // referenced by AMBefore: this is the set of values which folding in this 102984d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // address extends the lifetime of. 103084d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // 103184d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // Note that there are only two potential values being referenced here, 103284d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // BaseReg and ScaleReg (global addresses are always available, as are any 103384d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // folded immediates). 103484d1b40d448663050f12fb4dee052db907ac4748Chris Lattner Value *BaseReg = AMAfter.BaseReg, *ScaledReg = AMAfter.ScaledReg; 103584d1b40d448663050f12fb4dee052db907ac4748Chris Lattner 103684d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // If the BaseReg or ScaledReg was referenced by the previous addrmode, their 103784d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // lifetime wasn't extended by adding this instruction. 103884d1b40d448663050f12fb4dee052db907ac4748Chris Lattner if (ValueAlreadyLiveAtInst(BaseReg, AMBefore.BaseReg, AMBefore.ScaledReg)) 103984d1b40d448663050f12fb4dee052db907ac4748Chris Lattner BaseReg = 0; 104084d1b40d448663050f12fb4dee052db907ac4748Chris Lattner if (ValueAlreadyLiveAtInst(ScaledReg, AMBefore.BaseReg, AMBefore.ScaledReg)) 104184d1b40d448663050f12fb4dee052db907ac4748Chris Lattner ScaledReg = 0; 104284d1b40d448663050f12fb4dee052db907ac4748Chris Lattner 104384d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // If folding this instruction (and it's subexprs) didn't extend any live 104484d1b40d448663050f12fb4dee052db907ac4748Chris Lattner // ranges, we're ok with it. 104584d1b40d448663050f12fb4dee052db907ac4748Chris Lattner if (BaseReg == 0 && ScaledReg == 0) 104684d1b40d448663050f12fb4dee052db907ac4748Chris Lattner return true; 10475eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 10485eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // If all uses of this instruction are ultimately load/store/inlineasm's, 10495eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // check to see if their addressing modes will include this instruction. If 10505eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // so, we can fold it into all uses, so it doesn't matter if it has multiple 10515eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // uses. 10525eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner SmallVector<std::pair<Instruction*,unsigned>, 16> MemoryUses; 10535eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner SmallPtrSet<Instruction*, 16> ConsideredInsts; 1054695d8ec33b4303d05b3142fdfd78751193df9c4cChris Lattner if (FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TLI)) 10555eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return false; // Has a non-memory, non-foldable use! 10565eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 10575eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // Now that we know that all uses of this instruction are part of a chain of 10585eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // computation involving only operations that could theoretically be folded 10595eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // into a memory use, loop over each of these uses and see if they could 10605eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // *actually* fold the instruction. 10615eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner SmallVector<Instruction*, 32> MatchedAddrModeInsts; 10625eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner for (unsigned i = 0, e = MemoryUses.size(); i != e; ++i) { 10635eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner Instruction *User = MemoryUses[i].first; 10645eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner unsigned OpNo = MemoryUses[i].second; 10655eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 10665eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // Get the access type of this use. If the use isn't a pointer, we don't 10675eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // know what it accesses. 10685eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner Value *Address = User->getOperand(OpNo); 10695eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner if (!isa<PointerType>(Address->getType())) 10705eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return false; 10715eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner const Type *AddressAccessTy = 10725eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner cast<PointerType>(Address->getType())->getElementType(); 10735eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 10745eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // Do a match against the root of this address, ignoring profitability. This 10755eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // will tell us if the addressing mode for the memory operation will 10765eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // *actually* cover the shared instruction. 10775eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner ExtAddrMode Result; 10785eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI, AddressAccessTy, 1079896617b776e7b015346160645b19be776cbe3805Chris Lattner MemoryInst, Result); 10805eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner Matcher.IgnoreProfitability = true; 10815eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner bool Success = Matcher.MatchAddr(Address, 0); 10825eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner Success = Success; assert(Success && "Couldn't select *anything*?"); 10835eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 10845eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner // If the match didn't cover I, then it won't be shared by it. 10855eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner if (std::find(MatchedAddrModeInsts.begin(), MatchedAddrModeInsts.end(), 10865eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner I) == MatchedAddrModeInsts.end()) 10875eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return false; 10885eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 10895eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner MatchedAddrModeInsts.clear(); 10905eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner } 10915eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 10925eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner return true; 10935eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner} 10945eecb7f164a926540bc1bdffc7df81ab4ddce710Chris Lattner 1095dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 109688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 109788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner// Memory Optimization 109888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 109988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 1100dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// IsNonLocalValue - Return true if the specified values are defined in a 1101dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// different basic block than BB. 1102dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool IsNonLocalValue(Value *V, BasicBlock *BB) { 1103dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 1104dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return I->getParent() != BB; 1105dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 1106dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 1107dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 110888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// OptimizeMemoryInst - Load and Store Instructions have often have 1109dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// addressing modes that can do significant amounts of computation. As such, 1110dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// instruction selection will try to get the load or store to do as much 1111dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// computation as possible for the program. The problem is that isel can only 1112dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// see within a single block. As such, we sink as much legal addressing mode 1113dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// stuff into the block as possible. 111488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// 111588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// This method is used to optimize both load/store and inline asms with memory 111688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// operands. 1117896617b776e7b015346160645b19be776cbe3805Chris Lattnerbool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr, 111888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner const Type *AccessTy, 111988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner DenseMap<Value*,Value*> &SunkAddrs) { 1120dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Figure out what addressing mode will be built up for this operation. 1121dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SmallVector<Instruction*, 16> AddrModeInsts; 1122896617b776e7b015346160645b19be776cbe3805Chris Lattner ExtAddrMode AddrMode = AddressingModeMatcher::Match(Addr, AccessTy,MemoryInst, 1123896617b776e7b015346160645b19be776cbe3805Chris Lattner AddrModeInsts, *TLI); 1124692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1125dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if any of the instructions supersumed by this addr mode are 1126dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // non-local to I's BB. 1127dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool AnyNonLocal = false; 1128dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { 1129896617b776e7b015346160645b19be776cbe3805Chris Lattner if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) { 1130dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AnyNonLocal = true; 1131dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 1132dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 1133dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 1134692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1135dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If all the instructions matched are already in this BB, don't do anything. 1136dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!AnyNonLocal) { 1137dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DEBUG(cerr << "CGP: Found local addrmode: " << AddrMode << "\n"); 1138dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 1139dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 1140692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1141dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Insert this computation right after this user. Since our caller is 1142dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // scanning from the top of the BB to the bottom, reuse of the expr are 1143dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // guaranteed to happen later. 1144896617b776e7b015346160645b19be776cbe3805Chris Lattner BasicBlock::iterator InsertPt = MemoryInst; 1145692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1146dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Now that we determined the addressing expression we want to use and know 1147dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // that we have to sink it into this block. Check to see if we have already 1148dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done this for some other load/store instr in this block. If so, reuse the 1149dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // computation. 1150dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *&SunkAddr = SunkAddrs[Addr]; 1151dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr) { 1152dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DEBUG(cerr << "CGP: Reusing nonlocal addrmode: " << AddrMode << "\n"); 1153dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr->getType() != Addr->getType()) 1154dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new BitCastInst(SunkAddr, Addr->getType(), "tmp", InsertPt); 1155dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 1156dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DEBUG(cerr << "CGP: SINKING nonlocal addrmode: " << AddrMode << "\n"); 1157dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const Type *IntPtrTy = TLI->getTargetData()->getIntPtrType(); 1158692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1159dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *Result = 0; 1160dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Start with the scale value. 1161dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale) { 1162dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = AddrMode.ScaledReg; 1163dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (V->getType() == IntPtrTy) { 1164dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done. 1165dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (isa<PointerType>(V->getType())) { 1166dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 1167dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 1168dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cast<IntegerType>(V->getType())->getBitWidth()) { 1169dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new TruncInst(V, IntPtrTy, "sunkaddr", InsertPt); 1170dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 1171dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new SExtInst(V, IntPtrTy, "sunkaddr", InsertPt); 1172dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 1173dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale != 1) 11747cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif V = BinaryOperator::CreateMul(V, ConstantInt::get(IntPtrTy, 1175dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.Scale), 1176dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner "sunkaddr", InsertPt); 1177dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 1178dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 1179dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 1180dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the base register. 1181dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseReg) { 1182dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = AddrMode.BaseReg; 1183dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (V->getType() != IntPtrTy) 1184dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 1185dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 11867cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 1187dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 1188dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 1189dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 1190692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1191dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the BaseGV if present. 1192dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseGV) { 1193dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = new PtrToIntInst(AddrMode.BaseGV, IntPtrTy, "sunkaddr", 1194dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner InsertPt); 1195dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 11967cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 1197dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 1198dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 1199dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 1200692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1201dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the Base Offset if present. 1202dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseOffs) { 1203dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 1204dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 12057cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 1206dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 1207dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 1208dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 1209dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 1210dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result == 0) 1211dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = Constant::getNullValue(Addr->getType()); 1212dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 1213dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new IntToPtrInst(Result, Addr->getType(), "sunkaddr",InsertPt); 1214dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 1215692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1216896617b776e7b015346160645b19be776cbe3805Chris Lattner MemoryInst->replaceUsesOfWith(Addr, SunkAddr); 1217692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1218dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Addr->use_empty()) 12193481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner RecursivelyDeleteTriviallyDeadInstructions(Addr); 1220dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 1221dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 1222dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 12239bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// OptimizeInlineAsmInst - If there are any memory operands, use 122488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// OptimizeMemoryInst to sink their address computing into the block when 12259bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// possible / profitable. 12269bf12b5583104c810cfadcdce91edf9efad79973Evan Chengbool CodeGenPrepare::OptimizeInlineAsmInst(Instruction *I, CallSite CS, 12279bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng DenseMap<Value*,Value*> &SunkAddrs) { 12289bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng bool MadeChange = false; 12299bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng InlineAsm *IA = cast<InlineAsm>(CS.getCalledValue()); 12309bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 12319bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Do a prepass over the constraints, canonicalizing them, and building up the 12329bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // ConstraintOperands list. 12339bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng std::vector<InlineAsm::ConstraintInfo> 12349bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng ConstraintInfos = IA->ParseConstraints(); 12359bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 12369bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng /// ConstraintOperands - Information about all of the constraints. 12379bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng std::vector<TargetLowering::AsmOperandInfo> ConstraintOperands; 12389bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng unsigned ArgNo = 0; // ArgNo - The argument of the CallInst. 12399bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng for (unsigned i = 0, e = ConstraintInfos.size(); i != e; ++i) { 12409bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng ConstraintOperands. 12419bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng push_back(TargetLowering::AsmOperandInfo(ConstraintInfos[i])); 12429bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng TargetLowering::AsmOperandInfo &OpInfo = ConstraintOperands.back(); 12439bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 12449bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Compute the value type for each operand. 12459bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng switch (OpInfo.Type) { 12469bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng case InlineAsm::isOutput: 12479bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng if (OpInfo.isIndirect) 12489bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng OpInfo.CallOperandVal = CS.getArgument(ArgNo++); 12499bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng break; 12509bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng case InlineAsm::isInput: 12519bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng OpInfo.CallOperandVal = CS.getArgument(ArgNo++); 12529bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng break; 12539bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng case InlineAsm::isClobber: 12549bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Nothing to do. 12559bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng break; 12569bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng } 12579bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 12589bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Compute the constraint code and ConstraintType to use. 1259a7e6146688f4b1f0f0651af4df4994e78d438377Evan Cheng TLI->ComputeConstraintToUse(OpInfo, SDValue(), 1260a7e6146688f4b1f0f0651af4df4994e78d438377Evan Cheng OpInfo.ConstraintType == TargetLowering::C_Memory); 12619bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 12629ec8095485c994522c9a50e16fc029de94c20476Eli Friedman if (OpInfo.ConstraintType == TargetLowering::C_Memory && 12639ec8095485c994522c9a50e16fc029de94c20476Eli Friedman OpInfo.isIndirect) { 12649bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng Value *OpVal = OpInfo.CallOperandVal; 126588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner MadeChange |= OptimizeMemoryInst(I, OpVal, OpVal->getType(), SunkAddrs); 12669bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng } 12679bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng } 12689bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 12699bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng return MadeChange; 12709bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng} 12719bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 1272bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Chengbool CodeGenPrepare::OptimizeExtUses(Instruction *I) { 1273bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *DefBB = I->getParent(); 1274bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1275bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // If both result of the {s|z}xt and its source are live out, rewrite all 1276bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // other uses of the source with result of extension. 1277bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Value *Src = I->getOperand(0); 1278bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (Src->hasOneUse()) 1279bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 1280bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1281696e5c047bd06bf6b7b5471b3f4dec319b43628bEvan Cheng // Only do this xform if truncating is free. 128253bdbd756581a9a1d6d381059f103c5f3c687bb6Gabor Greif if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType())) 1283f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng return false; 1284f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng 1285772de516b6851e679d3da9e5171712b9c3122019Evan Cheng // Only safe to perform the optimization if the source is also defined in 1286765dff258545f019502023045b471443ff9ef6c4Evan Cheng // this block. 1287765dff258545f019502023045b471443ff9ef6c4Evan Cheng if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent()) 1288772de516b6851e679d3da9e5171712b9c3122019Evan Cheng return false; 1289772de516b6851e679d3da9e5171712b9c3122019Evan Cheng 1290bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool DefIsLiveOut = false; 1291692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 1292bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 1293bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 1294bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1295bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 1296bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 1297bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 1298bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DefIsLiveOut = true; 1299bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng break; 1300bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 1301bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!DefIsLiveOut) 1302bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 1303bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1304765dff258545f019502023045b471443ff9ef6c4Evan Cheng // Make sure non of the uses are PHI nodes. 1305692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 1306765dff258545f019502023045b471443ff9ef6c4Evan Cheng UI != E; ++UI) { 1307765dff258545f019502023045b471443ff9ef6c4Evan Cheng Instruction *User = cast<Instruction>(*UI); 1308f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng BasicBlock *UserBB = User->getParent(); 1309f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (UserBB == DefBB) continue; 1310f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // Be conservative. We don't want this xform to end up introducing 1311f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // reloads just before load / store instructions. 1312f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User)) 1313765dff258545f019502023045b471443ff9ef6c4Evan Cheng return false; 1314765dff258545f019502023045b471443ff9ef6c4Evan Cheng } 1315765dff258545f019502023045b471443ff9ef6c4Evan Cheng 1316bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // InsertedTruncs - Only insert one trunc in each block once. 1317bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DenseMap<BasicBlock*, Instruction*> InsertedTruncs; 1318bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1319bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool MadeChange = false; 1320692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 1321bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 1322bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Use &TheUse = UI.getUse(); 1323bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 1324bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1325bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 1326bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 1327bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 1328bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1329bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Both src and def are live in this block. Rewrite the use. 1330bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *&InsertedTrunc = InsertedTruncs[UserBB]; 1331bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1332bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!InsertedTrunc) { 133302dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 1334692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1335bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt); 1336bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 1337bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1338bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Replace a use of the {s|z}ext source with a use of the result. 1339bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng TheUse = InsertedTrunc; 1340bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1341bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange = true; 1342bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 1343bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1344bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return MadeChange; 1345bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng} 1346bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1347dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// In this pass we look for GEP and cast instructions that are used 1348dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// across basic blocks and rewrite them to improve basic-block-at-a-time 1349dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// selection. 1350dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { 1351dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 1352692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1353dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Split all critical edges where the dest block has a PHI and where the phi 1354dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // has shared immediate operands. 1355dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TerminatorInst *BBTI = BB.getTerminator(); 1356dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (BBTI->getNumSuccessors() > 1) { 1357dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (unsigned i = 0, e = BBTI->getNumSuccessors(); i != e; ++i) 1358dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (isa<PHINode>(BBTI->getSuccessor(i)->begin()) && 1359dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner isCriticalEdge(BBTI, i, true)) 1360dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner SplitEdgeNicely(BBTI, i, this); 1361dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 1362692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1363692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1364dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Keep track of non-local addresses that have been sunk into this block. 1365dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This allows us to avoid inserting duplicate code for blocks with multiple 1366dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // load/stores of the same address. 1367dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DenseMap<Value*, Value*> SunkAddrs; 1368692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1369dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (BasicBlock::iterator BBI = BB.begin(), E = BB.end(); BBI != E; ) { 1370dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *I = BBI++; 1371692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1372dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (CastInst *CI = dyn_cast<CastInst>(I)) { 1373dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If the source of the cast is a constant, then this should have 1374dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // already been constant folded. The only reason NOT to constant fold 1375dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // it is if something (e.g. LSR) was careful to place the constant 1376dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // evaluation in a block other than then one that uses it (e.g. to hoist 1377dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // the address of globals out of a loop). If this is the case, we don't 1378dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // want to forward-subst the cast. 1379dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (isa<Constant>(CI->getOperand(0))) 1380dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner continue; 1381692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1382bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool Change = false; 1383bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (TLI) { 1384bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Change = OptimizeNoopCopyExpression(CI, *TLI); 1385bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange |= Change; 1386bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 1387bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 138855e641b766a18878b51551d626d5a566102e487eEvan Cheng if (!Change && (isa<ZExtInst>(I) || isa<SExtInst>(I))) 1389bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange |= OptimizeExtUses(I); 1390ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } else if (CmpInst *CI = dyn_cast<CmpInst>(I)) { 1391ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen MadeChange |= OptimizeCmpExpression(CI); 1392dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 1393dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI) 139488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner MadeChange |= OptimizeMemoryInst(I, I->getOperand(0), LI->getType(), 139588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner SunkAddrs); 1396dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 1397dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI) 139888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner MadeChange |= OptimizeMemoryInst(I, SI->getOperand(1), 139988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner SI->getOperand(0)->getType(), 140088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner SunkAddrs); 1401dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 1402f25646bfb375b614cddcc8b6fda2b524feae1efaChris Lattner if (GEPI->hasAllZeroIndices()) { 1403dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner /// The GEP operand must be a pointer, so must its result -> BitCast 1404692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 1405dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->getName(), GEPI); 1406dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->replaceAllUsesWith(NC); 1407dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->eraseFromParent(); 1408dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner MadeChange = true; 1409dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner BBI = NC; 1410dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 1411dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (CallInst *CI = dyn_cast<CallInst>(I)) { 1412dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If we found an inline asm expession, and if the target knows how to 1413dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // lower it to normal LLVM code, do so now. 1414dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI && isa<InlineAsm>(CI->getCalledValue())) 1415692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher if (const TargetAsmInfo *TAI = 1416dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner TLI->getTargetMachine().getTargetAsmInfo()) { 1417dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TAI->ExpandInlineAsm(CI)) 1418dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner BBI = BB.begin(); 14199bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng else 14209bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Sink address computing for memory operands into the block. 14219bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng MadeChange |= OptimizeInlineAsmInst(I, &(*CI), SunkAddrs); 1422dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 1423dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 1424dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 1425692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1426dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 1427dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 1428