CodeGenPrepare.cpp revision a119de86a064414622562cfe32953de7f9b0ee40
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" 236aae1d6582fe8519c42d9774d670bb93c78e9637Dale Johannesen#include "llvm/IntrinsicInst.h" 24dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Pass.h" 25dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetAsmInfo.h" 26dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetData.h" 27dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetLowering.h" 28dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetMachine.h" 29a1fd5b386dd8eb4c86bfd2b9659c219a1c4f56dbEvan Cheng#include "llvm/Transforms/Utils/AddrModeMatcher.h" 30dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 31dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Transforms/Utils/Local.h" 32dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/ADT/DenseMap.h" 33dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/ADT/SmallSet.h" 3403ce042d70c423a41edca0714112a0e06b16493bDan Gohman#include "llvm/Assembly/Writer.h" 359bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng#include "llvm/Support/CallSite.h" 36ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng#include "llvm/Support/CommandLine.h" 37d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner#include "llvm/Support/Compiler.h" 38bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng#include "llvm/Support/Debug.h" 39dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 40088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner#include "llvm/Support/PatternMatch.h" 41dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerusing namespace llvm; 42088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattnerusing namespace llvm::PatternMatch; 43dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 44ab63152871f4144050d0a58d592a95e089fe40d4Evan Chengstatic cl::opt<bool> FactorCommonPreds("split-critical-paths-tweak", 45ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng cl::init(false), cl::Hidden); 46ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 47692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christophernamespace { 48dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner class VISIBILITY_HIDDEN CodeGenPrepare : public FunctionPass { 49dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// TLI - Keep a pointer of a TargetLowering to consult for determining 50dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// transformation profitability. 51dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner const TargetLowering *TLI; 52ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 53ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng /// BackEdges - Keep a set of all the loop back edges. 54ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng /// 55fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump SmallSet<std::pair<const BasicBlock*, const BasicBlock*>, 8> BackEdges; 56dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner public: 57ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 58c2bbfc18e9adbbdcf5b3375d8d25e2452f7df7f1Dan Gohman explicit CodeGenPrepare(const TargetLowering *tli = 0) 59ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman : FunctionPass(&ID), TLI(tli) {} 60dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool runOnFunction(Function &F); 61692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 62dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner private: 63d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool EliminateMostlyEmptyBlocks(Function &F); 64d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; 65d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner void EliminateMostlyEmptyBlock(BasicBlock *BB); 66dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool OptimizeBlock(BasicBlock &BB); 6788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner bool OptimizeMemoryInst(Instruction *I, Value *Addr, const Type *AccessTy, 6888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner DenseMap<Value*,Value*> &SunkAddrs); 699bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng bool OptimizeInlineAsmInst(Instruction *I, CallSite CS, 709bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng DenseMap<Value*,Value*> &SunkAddrs); 71bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool OptimizeExtUses(Instruction *I); 72fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump void findLoopBackEdges(const Function &F); 73dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner }; 74dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 75794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 761997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar CodeGenPrepare::ID = 0; 77dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerstatic RegisterPass<CodeGenPrepare> X("codegenprepare", 78dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner "Optimize for code generation"); 79dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 80dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris LattnerFunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { 81dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return new CodeGenPrepare(TLI); 82dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 83dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 84ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng/// findLoopBackEdges - Do a DFS walk to find loop back edges. 85ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng/// 86fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stumpvoid CodeGenPrepare::findLoopBackEdges(const Function &F) { 87fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges; 88fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump FindFunctionBackedges(F, Edges); 89fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump 90fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump BackEdges.insert(Edges.begin(), Edges.end()); 91ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng} 92ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 93dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 94dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::runOnFunction(Function &F) { 95dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool EverMadeChange = false; 96692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 97d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // First pass, eliminate blocks that contain only PHI nodes and an 98d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // unconditional branch. 99d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EverMadeChange |= EliminateMostlyEmptyBlocks(F); 100692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1017e66c0d43aefce78948f0b73422f6e5bb28e2077Evan Cheng // Now find loop back edges. 1027e66c0d43aefce78948f0b73422f6e5bb28e2077Evan Cheng findLoopBackEdges(F); 1037e66c0d43aefce78948f0b73422f6e5bb28e2077Evan Cheng 104d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = true; 105dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner while (MadeChange) { 106dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = false; 107dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 108dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange |= OptimizeBlock(*BB); 109dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner EverMadeChange |= MadeChange; 110dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 111dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return EverMadeChange; 112dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 113dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 1142d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes, 1152d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// debug info directives, and an unconditional branch. Passes before isel 1162d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// (e.g. LSR/loopsimplify) often split edges in ways that are non-optimal for 1172d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// isel. Start by eliminating these blocks so we can split them the way we 1182d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// want them. 119d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) { 120d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = false; 121d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Note that this intentionally skips the entry block. 122d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) { 123d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *BB = I++; 124d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 125d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If this block doesn't end with an uncond branch, ignore it. 126d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 127d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!BI || !BI->isUnconditional()) 128d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 129692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1302d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen // If the instruction before the branch (skipping debug info) isn't a phi 1312d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen // node, then other stuff is happening here. 132d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::iterator BBI = BI; 133d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBI != BB->begin()) { 134d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner --BBI; 1352d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen while (isa<DbgInfoIntrinsic>(BBI)) { 1362d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen if (BBI == BB->begin()) 1372d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen break; 1382d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen --BBI; 1392d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen } 1402d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI)) 1412d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen continue; 142d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 143692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 144d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Do not break infinite loops. 145d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 146d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (DestBB == BB) 147d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 148692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 149d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!CanMergeBlocks(BB, DestBB)) 150d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 151692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 152d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EliminateMostlyEmptyBlock(BB); 153d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner MadeChange = true; 154d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 155d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return MadeChange; 156d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 157d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 158d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a 159d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// single uncond branch between them, and BB contains no other non-phi 160d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// instructions. 161d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, 162d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const BasicBlock *DestBB) const { 163d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // We only want to eliminate blocks whose phi nodes are used by phi nodes in 164d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // the successor. If there are more complex condition (e.g. preheaders), 165d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // don't mess around with them. 166d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::const_iterator BBI = BB->begin(); 167d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 168d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (Value::use_const_iterator UI = PN->use_begin(), E = PN->use_end(); 169d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner UI != E; ++UI) { 170d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Instruction *User = cast<Instruction>(*UI); 171d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (User->getParent() != DestBB || !isa<PHINode>(User)) 172d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return false; 173692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If User is inside DestBB block and it is a PHINode then check 174692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // incoming value. If incoming value is not from BB then this is 17575abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel // a complex condition (e.g. preheaders) we want to avoid here. 17675abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (User->getParent() == DestBB) { 17775abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (const PHINode *UPN = dyn_cast<PHINode>(User)) 17875abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { 17975abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); 18075abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (Insn && Insn->getParent() == BB && 18175abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Insn->getParent() != UPN->getIncomingBlock(I)) 18275abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel return false; 18375abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 18475abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 185d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 186d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 187692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 188d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If BB and DestBB contain any common predecessors, then the phi nodes in BB 189d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // and DestBB may have conflicting incoming values for the block. If so, we 190d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // can't merge the block. 191d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); 192d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!DestBBPN) return true; // no conflict. 193692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 194d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Collect the preds of BB. 195f67f73a519eac94b6c1f98dbce7d251a3a4aea07Chris Lattner SmallPtrSet<const BasicBlock*, 16> BBPreds; 196d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 197d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // It is faster to get preds from a PHI than with pred_iterator. 198d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 199d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(BBPN->getIncomingBlock(i)); 200d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 201d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(pred_begin(BB), pred_end(BB)); 202d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 203692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 204d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Walk the preds of DestBB. 205d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { 206d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *Pred = DestBBPN->getIncomingBlock(i); 207d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBPreds.count(Pred)) { // Common predecessor? 208d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBI = DestBB->begin(); 209d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 210d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V1 = PN->getIncomingValueForBlock(Pred); 211d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V2 = PN->getIncomingValueForBlock(BB); 212692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 213d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If V2 is a phi node in BB, look up what the mapped value will be. 214d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) 215d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V2PN->getParent() == BB) 216d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner V2 = V2PN->getIncomingValueForBlock(Pred); 217692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 218d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If there is a conflict, bail out. 219d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V1 != V2) return false; 220d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 221d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 222d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 223d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 224d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return true; 225d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 226d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 227d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 228d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and 229d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// an unconditional branch in it. 230d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnervoid CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { 231d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 232d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 233692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 234d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner DOUT << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB; 235692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 236d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If the destination block has a single pred, then this is a trivial edge, 237d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // just collapse it. 2389918fb5631974f2201a640384b7ebe672c749e43Chris Lattner if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) { 239f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (SinglePred != DestBB) { 240f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // Remember if SinglePred was the entry block of the function. If so, we 241f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // will need to move BB back to the entry position. 242f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 243f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner MergeBasicBlockIntoOnlyPred(DestBB); 244f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 245f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (isEntry && BB != &BB->getParent()->getEntryBlock()) 246f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner BB->moveBefore(&BB->getParent()->getEntryBlock()); 247f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 248f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner DOUT << "AFTER:\n" << *DestBB << "\n\n\n"; 249f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner return; 250f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner } 251d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 252692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 253d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB 254d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // to handle the new incoming edges it is about to have. 255d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *PN; 256d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (BasicBlock::iterator BBI = DestBB->begin(); 257d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 258d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Remove the incoming value for BB, and remember it. 259d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner Value *InVal = PN->removeIncomingValue(BB, false); 260692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 261d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Two options: either the InVal is a phi node defined in BB or it is some 262d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // value that dominates BB. 263d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *InValPhi = dyn_cast<PHINode>(InVal); 264d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (InValPhi && InValPhi->getParent() == BB) { 265d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Add all of the input values of the input PHI as inputs of this phi. 266d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) 267d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InValPhi->getIncomingValue(i), 268d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner InValPhi->getIncomingBlock(i)); 269d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 270d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, add one instance of the dominating value for each edge that 271d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // we will be adding. 272d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 273d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 274d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); 275d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 276d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 277d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, *PI); 278d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 279d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 280d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 281692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 282d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // The PHIs are now updated, change everything that refers to BB to use 283d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // DestBB and remove BB. 284d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->replaceAllUsesWith(DestBB); 285d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->eraseFromParent(); 286692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 287d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner DOUT << "AFTER:\n" << *DestBB << "\n\n\n"; 288d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 289d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 290d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 291ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner/// SplitEdgeNicely - Split the critical edge from TI to its specified 292dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// successor if it will improve codegen. We only do this if the successor has 293dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// phi nodes (otherwise critical edges are ok). If there is already another 294dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// predecessor of the succ that is empty (and thus has no phi nodes), use it 295dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// instead of introducing a new block. 296ab63152871f4144050d0a58d592a95e089fe40d4Evan Chengstatic void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, 297fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump SmallSet<std::pair<const BasicBlock*, 298fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump const BasicBlock*>, 8> &BackEdges, 299ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng Pass *P) { 300dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *TIBB = TI->getParent(); 301dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *Dest = TI->getSuccessor(SuccNum); 302dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner assert(isa<PHINode>(Dest->begin()) && 303dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner "This should only be called if Dest has a PHI!"); 304692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 305fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng // Do not split edges to EH landing pads. 306fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng if (InvokeInst *Invoke = dyn_cast<InvokeInst>(TI)) { 307fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng if (Invoke->getSuccessor(1) == Dest) 308fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng return; 309fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng } 310fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng 311ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner // As a hack, never split backedges of loops. Even though the copy for any 312ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner // PHIs inserted on the backedge would be dead for exits from the loop, we 313ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner // assume that the cost of *splitting* the backedge would be too high. 314ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng if (BackEdges.count(std::make_pair(TIBB, Dest))) 315ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner return; 316692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 317ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng if (!FactorCommonPreds) { 318ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng /// TIPHIValues - This array is lazily computed to determine the values of 319ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng /// PHIs in Dest that TI would provide. 320ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng SmallVector<Value*, 32> TIPHIValues; 321ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 322ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng // Check to see if Dest has any blocks that can be used as a split edge for 323ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng // this terminator. 324ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng for (pred_iterator PI = pred_begin(Dest), E = pred_end(Dest); PI != E; ++PI) { 325ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng BasicBlock *Pred = *PI; 326ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng // To be usable, the pred has to end with an uncond branch to the dest. 327ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator()); 3286aae1d6582fe8519c42d9774d670bb93c78e9637Dale Johannesen if (!PredBr || !PredBr->isUnconditional()) 3296aae1d6582fe8519c42d9774d670bb93c78e9637Dale Johannesen continue; 3306aae1d6582fe8519c42d9774d670bb93c78e9637Dale Johannesen // Must be empty other than the branch and debug info. 3316aae1d6582fe8519c42d9774d670bb93c78e9637Dale Johannesen BasicBlock::iterator I = Pred->begin(); 3326aae1d6582fe8519c42d9774d670bb93c78e9637Dale Johannesen while (isa<DbgInfoIntrinsic>(I)) 3336aae1d6582fe8519c42d9774d670bb93c78e9637Dale Johannesen I++; 3346aae1d6582fe8519c42d9774d670bb93c78e9637Dale Johannesen if (dyn_cast<Instruction>(I) != PredBr) 3356aae1d6582fe8519c42d9774d670bb93c78e9637Dale Johannesen continue; 3366aae1d6582fe8519c42d9774d670bb93c78e9637Dale Johannesen // Cannot be the entry block; its label does not get emitted. 3376aae1d6582fe8519c42d9774d670bb93c78e9637Dale Johannesen if (Pred == &(Dest->getParent()->getEntryBlock())) 338ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng continue; 339ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 340ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng // Finally, since we know that Dest has phi nodes in it, we have to make 3416aae1d6582fe8519c42d9774d670bb93c78e9637Dale Johannesen // sure that jumping to Pred will have the same effect as going to Dest in 342ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng // terms of PHI values. 343ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng PHINode *PN; 344ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng unsigned PHINo = 0; 345ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng bool FoundMatch = true; 346ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng for (BasicBlock::iterator I = Dest->begin(); 347ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) { 348ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng if (PHINo == TIPHIValues.size()) 349ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng TIPHIValues.push_back(PN->getIncomingValueForBlock(TIBB)); 350ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 351ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng // If the PHI entry doesn't work, we can't use this pred. 352ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng if (TIPHIValues[PHINo] != PN->getIncomingValueForBlock(Pred)) { 353ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng FoundMatch = false; 354ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng break; 355ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng } 356ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng } 357692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 358ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng // If we found a workable predecessor, change TI to branch to Succ. 359ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng if (FoundMatch) { 360ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng Dest->removePredecessor(TIBB); 361ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng TI->setSuccessor(SuccNum, Pred); 362ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng return; 363dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 364dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 365692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 366ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng SplitCriticalEdge(TI, SuccNum, P, true); 367ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng return; 368ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng } 369ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 370ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng PHINode *PN; 371ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng SmallVector<Value*, 8> TIPHIValues; 372ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng for (BasicBlock::iterator I = Dest->begin(); 373ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng (PN = dyn_cast<PHINode>(I)); ++I) 374ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng TIPHIValues.push_back(PN->getIncomingValueForBlock(TIBB)); 375ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 376ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng SmallVector<BasicBlock*, 8> IdenticalPreds; 377ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng for (pred_iterator PI = pred_begin(Dest), E = pred_end(Dest); PI != E; ++PI) { 378ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng BasicBlock *Pred = *PI; 379ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng if (BackEdges.count(std::make_pair(Pred, Dest))) 380ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng continue; 381ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng if (PI == TIBB) 382ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng IdenticalPreds.push_back(Pred); 383ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng else { 384ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng bool Identical = true; 385ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng unsigned PHINo = 0; 386ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng for (BasicBlock::iterator I = Dest->begin(); 387ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) 388ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng if (TIPHIValues[PHINo] != PN->getIncomingValueForBlock(Pred)) { 389ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng Identical = false; 390ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng break; 391ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng } 392ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng if (Identical) 393ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng IdenticalPreds.push_back(Pred); 394dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 395dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 396692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 397ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng assert(!IdenticalPreds.empty()); 398ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng SplitBlockPredecessors(Dest, &IdenticalPreds[0], IdenticalPreds.size(), 399ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng ".critedge", P); 400dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 401dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 402ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 403dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// OptimizeNoopCopyExpression - If the specified cast instruction is a noop 404a119de86a064414622562cfe32953de7f9b0ee40Dan Gohman/// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC), 405a119de86a064414622562cfe32953de7f9b0ee40Dan Gohman/// sink it into user blocks to reduce the number of virtual 406ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// registers that must be created and coalesced. 407dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// 408dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// Return true if any changes are made. 40985fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner/// 410dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){ 411692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If this is a noop copy, 41283ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands MVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 41383ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands MVT DstVT = TLI.getValueType(CI->getType()); 414692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 415dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This is an fp<->int conversion? 41683ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands if (SrcVT.isInteger() != DstVT.isInteger()) 417dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 4188e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands 419dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is an extension, it will be a zero or sign extension, which 420dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // isn't a noop. 4218e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands if (SrcVT.bitsLT(DstVT)) return false; 422692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 423dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If these values will be promoted, find out what they will be promoted 424dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // to. This helps us consider truncates on PPC as noop copies when they 425dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // are. 426dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) 427dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SrcVT = TLI.getTypeToTransformTo(SrcVT); 428dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.getTypeAction(DstVT) == TargetLowering::Promote) 429dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DstVT = TLI.getTypeToTransformTo(DstVT); 430692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 431dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If, after promotion, these are the same types, this is a noop copy. 432dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SrcVT != DstVT) 433dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 434692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 435dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *DefBB = CI->getParent(); 436692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 437dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// InsertedCasts - Only insert a cast in each block once. 438ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CastInst*> InsertedCasts; 439692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 440dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 441692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 442dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner UI != E; ) { 443dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Use &TheUse = UI.getUse(); 444dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *User = cast<Instruction>(*UI); 445692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 446dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Figure out which BB this cast is used in. For PHI's this is the 447dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // appropriate predecessor block. 448dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *UserBB = User->getParent(); 449dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) { 450a36791da41cf4f635e50077b290676b873836bdaGabor Greif UserBB = PN->getIncomingBlock(UI); 451dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 452692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 453dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Preincrement use iterator so we don't invalidate it. 454dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner ++UI; 455692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 456dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If this user is in the same block as the cast, don't change the cast. 457dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (UserBB == DefBB) continue; 458692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 459dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we have already inserted a cast into this block, use it. 460dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CastInst *&InsertedCast = InsertedCasts[UserBB]; 461dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 462dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (!InsertedCast) { 46302dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 464692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 465692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCast = 466692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 467dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner InsertPt); 468dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = true; 469dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 470692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 471ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cast with a use of the new cast. 472dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TheUse = InsertedCast; 473dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 474692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 475dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we removed all uses, nuke the cast. 476e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands if (CI->use_empty()) { 477dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CI->eraseFromParent(); 478e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands MadeChange = true; 479e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands } 480692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 481dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 482dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 483dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 484692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher/// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce 485ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// the number of virtual registers that must be created and coalesced. This is 486684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// a clear win except on targets with multiple condition code registers 487684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// (PowerPC), where it might lose; some adjustment may be wanted there. 488ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// 489ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// Return true if any changes are made. 49085fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattnerstatic bool OptimizeCmpExpression(CmpInst *CI) { 491ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *DefBB = CI->getParent(); 492692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 493ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen /// InsertedCmp - Only insert a cmp in each block once. 494ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CmpInst*> InsertedCmps; 495692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 496ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen bool MadeChange = false; 497692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 498ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen UI != E; ) { 499ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Use &TheUse = UI.getUse(); 500ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Instruction *User = cast<Instruction>(*UI); 501692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 502ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Preincrement use iterator so we don't invalidate it. 503ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen ++UI; 504692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 505ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Don't bother for PHI nodes. 506ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (isa<PHINode>(User)) 507ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen continue; 508ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 509ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Figure out which BB this cmp is used in. 510ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *UserBB = User->getParent(); 511692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 512ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If this user is in the same block as the cmp, don't change the cmp. 513ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (UserBB == DefBB) continue; 514692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 515ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we have already inserted a cmp into this block, use it. 516ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CmpInst *&InsertedCmp = InsertedCmps[UserBB]; 517ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 518ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (!InsertedCmp) { 51902dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 520692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 521692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCmp = 522692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher CmpInst::Create(CI->getOpcode(), CI->getPredicate(), CI->getOperand(0), 523ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->getOperand(1), "", InsertPt); 524ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen MadeChange = true; 525ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 526692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 527ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cmp with a use of the new cmp. 528ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen TheUse = InsertedCmp; 529ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 530692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 531ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we removed all uses, nuke the cmp. 532ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (CI->use_empty()) 533ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->eraseFromParent(); 534692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 535ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen return MadeChange; 536ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen} 537ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 53888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 53988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner// Memory Optimization 54088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 54188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 542dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// IsNonLocalValue - Return true if the specified values are defined in a 543dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// different basic block than BB. 544dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool IsNonLocalValue(Value *V, BasicBlock *BB) { 545dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 546dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return I->getParent() != BB; 547dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 548dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 549dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 55088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// OptimizeMemoryInst - Load and Store Instructions have often have 551dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// addressing modes that can do significant amounts of computation. As such, 552dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// instruction selection will try to get the load or store to do as much 553dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// computation as possible for the program. The problem is that isel can only 554dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// see within a single block. As such, we sink as much legal addressing mode 555dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// stuff into the block as possible. 55688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// 55788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// This method is used to optimize both load/store and inline asms with memory 55888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// operands. 559896617b776e7b015346160645b19be776cbe3805Chris Lattnerbool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr, 56088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner const Type *AccessTy, 56188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner DenseMap<Value*,Value*> &SunkAddrs) { 562dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Figure out what addressing mode will be built up for this operation. 563dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SmallVector<Instruction*, 16> AddrModeInsts; 564896617b776e7b015346160645b19be776cbe3805Chris Lattner ExtAddrMode AddrMode = AddressingModeMatcher::Match(Addr, AccessTy,MemoryInst, 565896617b776e7b015346160645b19be776cbe3805Chris Lattner AddrModeInsts, *TLI); 566692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 567dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if any of the instructions supersumed by this addr mode are 568dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // non-local to I's BB. 569dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool AnyNonLocal = false; 570dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { 571896617b776e7b015346160645b19be776cbe3805Chris Lattner if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) { 572dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AnyNonLocal = true; 573dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 574dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 575dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 576692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 577dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If all the instructions matched are already in this BB, don't do anything. 578dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!AnyNonLocal) { 579dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DEBUG(cerr << "CGP: Found local addrmode: " << AddrMode << "\n"); 580dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 581dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 582692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 583dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Insert this computation right after this user. Since our caller is 584dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // scanning from the top of the BB to the bottom, reuse of the expr are 585dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // guaranteed to happen later. 586896617b776e7b015346160645b19be776cbe3805Chris Lattner BasicBlock::iterator InsertPt = MemoryInst; 587692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 588dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Now that we determined the addressing expression we want to use and know 589dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // that we have to sink it into this block. Check to see if we have already 590dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done this for some other load/store instr in this block. If so, reuse the 591dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // computation. 592dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *&SunkAddr = SunkAddrs[Addr]; 593dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr) { 59465c02fbf9bda089398a67c887e32a99799afa522Chris Lattner DEBUG(cerr << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for " 59565c02fbf9bda089398a67c887e32a99799afa522Chris Lattner << *MemoryInst); 596dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr->getType() != Addr->getType()) 597dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new BitCastInst(SunkAddr, Addr->getType(), "tmp", InsertPt); 598dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 59965c02fbf9bda089398a67c887e32a99799afa522Chris Lattner DEBUG(cerr << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for " 60065c02fbf9bda089398a67c887e32a99799afa522Chris Lattner << *MemoryInst); 601dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const Type *IntPtrTy = TLI->getTargetData()->getIntPtrType(); 602692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 603dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *Result = 0; 604dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Start with the scale value. 605dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale) { 606dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = AddrMode.ScaledReg; 607dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (V->getType() == IntPtrTy) { 608dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done. 609dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (isa<PointerType>(V->getType())) { 610dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 611dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 612dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cast<IntegerType>(V->getType())->getBitWidth()) { 613dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new TruncInst(V, IntPtrTy, "sunkaddr", InsertPt); 614dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 615dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new SExtInst(V, IntPtrTy, "sunkaddr", InsertPt); 616dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 617dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale != 1) 6187cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif V = BinaryOperator::CreateMul(V, ConstantInt::get(IntPtrTy, 619dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.Scale), 620dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner "sunkaddr", InsertPt); 621dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 622dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 623dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 624dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the base register. 625dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseReg) { 626dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = AddrMode.BaseReg; 6278b0d4f61bbe07060a4638ae1d3731dec09d13854Dan Gohman if (isa<PointerType>(V->getType())) 628dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 6298b0d4f61bbe07060a4638ae1d3731dec09d13854Dan Gohman if (V->getType() != IntPtrTy) 6308b0d4f61bbe07060a4638ae1d3731dec09d13854Dan Gohman V = CastInst::CreateIntegerCast(V, IntPtrTy, /*isSigned=*/true, 6318b0d4f61bbe07060a4638ae1d3731dec09d13854Dan Gohman "sunkaddr", InsertPt); 632dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 6337cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 634dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 635dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 636dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 637692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 638dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the BaseGV if present. 639dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseGV) { 640dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = new PtrToIntInst(AddrMode.BaseGV, IntPtrTy, "sunkaddr", 641dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner InsertPt); 642dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 6437cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 644dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 645dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 646dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 647692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 648dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the Base Offset if present. 649dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseOffs) { 650dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 651dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 6527cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 653dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 654dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 655dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 656dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 657dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result == 0) 658dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = Constant::getNullValue(Addr->getType()); 659dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 660dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new IntToPtrInst(Result, Addr->getType(), "sunkaddr",InsertPt); 661dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 662692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 663896617b776e7b015346160645b19be776cbe3805Chris Lattner MemoryInst->replaceUsesOfWith(Addr, SunkAddr); 664692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 665dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Addr->use_empty()) 6663481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner RecursivelyDeleteTriviallyDeadInstructions(Addr); 667dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 668dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 669dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 6709bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// OptimizeInlineAsmInst - If there are any memory operands, use 67188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// OptimizeMemoryInst to sink their address computing into the block when 6729bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// possible / profitable. 6739bf12b5583104c810cfadcdce91edf9efad79973Evan Chengbool CodeGenPrepare::OptimizeInlineAsmInst(Instruction *I, CallSite CS, 6749bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng DenseMap<Value*,Value*> &SunkAddrs) { 6759bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng bool MadeChange = false; 6769bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng InlineAsm *IA = cast<InlineAsm>(CS.getCalledValue()); 6779bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 6789bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Do a prepass over the constraints, canonicalizing them, and building up the 6799bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // ConstraintOperands list. 6809bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng std::vector<InlineAsm::ConstraintInfo> 6819bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng ConstraintInfos = IA->ParseConstraints(); 6829bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 6839bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng /// ConstraintOperands - Information about all of the constraints. 6849bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng std::vector<TargetLowering::AsmOperandInfo> ConstraintOperands; 6859bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng unsigned ArgNo = 0; // ArgNo - The argument of the CallInst. 6869bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng for (unsigned i = 0, e = ConstraintInfos.size(); i != e; ++i) { 6879bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng ConstraintOperands. 6889bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng push_back(TargetLowering::AsmOperandInfo(ConstraintInfos[i])); 6899bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng TargetLowering::AsmOperandInfo &OpInfo = ConstraintOperands.back(); 6909bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 6919bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Compute the value type for each operand. 6929bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng switch (OpInfo.Type) { 6939bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng case InlineAsm::isOutput: 6949bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng if (OpInfo.isIndirect) 6959bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng OpInfo.CallOperandVal = CS.getArgument(ArgNo++); 6969bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng break; 6979bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng case InlineAsm::isInput: 6989bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng OpInfo.CallOperandVal = CS.getArgument(ArgNo++); 6999bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng break; 7009bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng case InlineAsm::isClobber: 7019bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Nothing to do. 7029bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng break; 7039bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng } 7049bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 7059bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Compute the constraint code and ConstraintType to use. 706a7e6146688f4b1f0f0651af4df4994e78d438377Evan Cheng TLI->ComputeConstraintToUse(OpInfo, SDValue(), 707a7e6146688f4b1f0f0651af4df4994e78d438377Evan Cheng OpInfo.ConstraintType == TargetLowering::C_Memory); 7089bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 7099ec8095485c994522c9a50e16fc029de94c20476Eli Friedman if (OpInfo.ConstraintType == TargetLowering::C_Memory && 7109ec8095485c994522c9a50e16fc029de94c20476Eli Friedman OpInfo.isIndirect) { 7119bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng Value *OpVal = OpInfo.CallOperandVal; 71288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner MadeChange |= OptimizeMemoryInst(I, OpVal, OpVal->getType(), SunkAddrs); 7139bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng } 7149bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng } 7159bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 7169bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng return MadeChange; 7179bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng} 7189bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 719bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Chengbool CodeGenPrepare::OptimizeExtUses(Instruction *I) { 720bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *DefBB = I->getParent(); 721bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 722bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // If both result of the {s|z}xt and its source are live out, rewrite all 723bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // other uses of the source with result of extension. 724bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Value *Src = I->getOperand(0); 725bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (Src->hasOneUse()) 726bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 727bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 728696e5c047bd06bf6b7b5471b3f4dec319b43628bEvan Cheng // Only do this xform if truncating is free. 72953bdbd756581a9a1d6d381059f103c5f3c687bb6Gabor Greif if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType())) 730f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng return false; 731f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng 732772de516b6851e679d3da9e5171712b9c3122019Evan Cheng // Only safe to perform the optimization if the source is also defined in 733765dff258545f019502023045b471443ff9ef6c4Evan Cheng // this block. 734765dff258545f019502023045b471443ff9ef6c4Evan Cheng if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent()) 735772de516b6851e679d3da9e5171712b9c3122019Evan Cheng return false; 736772de516b6851e679d3da9e5171712b9c3122019Evan Cheng 737bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool DefIsLiveOut = false; 738692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 739bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 740bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 741bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 742bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 743bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 744bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 745bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DefIsLiveOut = true; 746bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng break; 747bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 748bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!DefIsLiveOut) 749bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 750bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 751765dff258545f019502023045b471443ff9ef6c4Evan Cheng // Make sure non of the uses are PHI nodes. 752692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 753765dff258545f019502023045b471443ff9ef6c4Evan Cheng UI != E; ++UI) { 754765dff258545f019502023045b471443ff9ef6c4Evan Cheng Instruction *User = cast<Instruction>(*UI); 755f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng BasicBlock *UserBB = User->getParent(); 756f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (UserBB == DefBB) continue; 757f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // Be conservative. We don't want this xform to end up introducing 758f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // reloads just before load / store instructions. 759f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User)) 760765dff258545f019502023045b471443ff9ef6c4Evan Cheng return false; 761765dff258545f019502023045b471443ff9ef6c4Evan Cheng } 762765dff258545f019502023045b471443ff9ef6c4Evan Cheng 763bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // InsertedTruncs - Only insert one trunc in each block once. 764bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DenseMap<BasicBlock*, Instruction*> InsertedTruncs; 765bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 766bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool MadeChange = false; 767692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 768bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 769bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Use &TheUse = UI.getUse(); 770bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 771bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 772bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 773bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 774bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 775bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 776bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Both src and def are live in this block. Rewrite the use. 777bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *&InsertedTrunc = InsertedTruncs[UserBB]; 778bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 779bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!InsertedTrunc) { 78002dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 781692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 782bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt); 783bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 784bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 785bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Replace a use of the {s|z}ext source with a use of the result. 786bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng TheUse = InsertedTrunc; 787bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 788bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange = true; 789bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 790bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 791bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return MadeChange; 792bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng} 793bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 794dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// In this pass we look for GEP and cast instructions that are used 795dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// across basic blocks and rewrite them to improve basic-block-at-a-time 796dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// selection. 797dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { 798dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 799692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 800ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng // Split all critical edges where the dest block has a PHI. 801dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TerminatorInst *BBTI = BB.getTerminator(); 802dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (BBTI->getNumSuccessors() > 1) { 803ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng for (unsigned i = 0, e = BBTI->getNumSuccessors(); i != e; ++i) { 804ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng BasicBlock *SuccBB = BBTI->getSuccessor(i); 805ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng if (isa<PHINode>(SuccBB->begin()) && isCriticalEdge(BBTI, i, true)) 806ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng SplitEdgeNicely(BBTI, i, BackEdges, this); 807ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng } 808dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 809692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 810dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Keep track of non-local addresses that have been sunk into this block. 811dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This allows us to avoid inserting duplicate code for blocks with multiple 812dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // load/stores of the same address. 813dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DenseMap<Value*, Value*> SunkAddrs; 814692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 815dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (BasicBlock::iterator BBI = BB.begin(), E = BB.end(); BBI != E; ) { 816dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *I = BBI++; 817692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 818dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (CastInst *CI = dyn_cast<CastInst>(I)) { 819dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If the source of the cast is a constant, then this should have 820dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // already been constant folded. The only reason NOT to constant fold 821dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // it is if something (e.g. LSR) was careful to place the constant 822dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // evaluation in a block other than then one that uses it (e.g. to hoist 823dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // the address of globals out of a loop). If this is the case, we don't 824dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // want to forward-subst the cast. 825dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (isa<Constant>(CI->getOperand(0))) 826dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner continue; 827692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 828bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool Change = false; 829bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (TLI) { 830bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Change = OptimizeNoopCopyExpression(CI, *TLI); 831bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange |= Change; 832bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 833bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 83455e641b766a18878b51551d626d5a566102e487eEvan Cheng if (!Change && (isa<ZExtInst>(I) || isa<SExtInst>(I))) 835bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange |= OptimizeExtUses(I); 836ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } else if (CmpInst *CI = dyn_cast<CmpInst>(I)) { 837ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen MadeChange |= OptimizeCmpExpression(CI); 838dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 839dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI) 84088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner MadeChange |= OptimizeMemoryInst(I, I->getOperand(0), LI->getType(), 84188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner SunkAddrs); 842dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 843dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI) 84488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner MadeChange |= OptimizeMemoryInst(I, SI->getOperand(1), 84588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner SI->getOperand(0)->getType(), 84688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner SunkAddrs); 847dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 848f25646bfb375b614cddcc8b6fda2b524feae1efaChris Lattner if (GEPI->hasAllZeroIndices()) { 849dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner /// The GEP operand must be a pointer, so must its result -> BitCast 850692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 851dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->getName(), GEPI); 852dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->replaceAllUsesWith(NC); 853dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->eraseFromParent(); 854dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner MadeChange = true; 855dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner BBI = NC; 856dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 857dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (CallInst *CI = dyn_cast<CallInst>(I)) { 858dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If we found an inline asm expession, and if the target knows how to 859dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // lower it to normal LLVM code, do so now. 860dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI && isa<InlineAsm>(CI->getCalledValue())) 861692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher if (const TargetAsmInfo *TAI = 862dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner TLI->getTargetMachine().getTargetAsmInfo()) { 86365c02fbf9bda089398a67c887e32a99799afa522Chris Lattner if (TAI->ExpandInlineAsm(CI)) { 864dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner BBI = BB.begin(); 86565c02fbf9bda089398a67c887e32a99799afa522Chris Lattner // Avoid processing instructions out of order, which could cause 86665c02fbf9bda089398a67c887e32a99799afa522Chris Lattner // reuse before a value is defined. 86765c02fbf9bda089398a67c887e32a99799afa522Chris Lattner SunkAddrs.clear(); 86865c02fbf9bda089398a67c887e32a99799afa522Chris Lattner } else 8699bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Sink address computing for memory operands into the block. 8709bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng MadeChange |= OptimizeInlineAsmInst(I, &(*CI), SunkAddrs); 871dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 872dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 873dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 874692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 875dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 876dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 877