CodeGenPrepare.cpp revision 31ff1333e0651192212cee6e090df2ff57d19b53
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" 25d5f8684b16057df73771b23e293b400cb327e079Owen Anderson#include "llvm/Analysis/InstructionSimplify.h" 26ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter#include "llvm/Analysis/ProfileInfo.h" 27dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetData.h" 28dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetLowering.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" 32040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher#include "llvm/Transforms/Utils/BuildLibCalls.h" 33dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/ADT/DenseMap.h" 34dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/ADT/SmallSet.h" 357eb589d3f9294dbfe4d5205045bd8119a9666532Jakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 3603ce042d70c423a41edca0714112a0e06b16493bDan Gohman#include "llvm/Assembly/Writer.h" 379bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng#include "llvm/Support/CallSite.h" 38e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng#include "llvm/Support/CommandLine.h" 39bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng#include "llvm/Support/Debug.h" 40dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 41088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner#include "llvm/Support/PatternMatch.h" 426c1980b3357207c4d756255bc5e32323eac278dcDan Gohman#include "llvm/Support/raw_ostream.h" 43040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher#include "llvm/Support/IRBuilder.h" 44dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerusing namespace llvm; 45088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattnerusing namespace llvm::PatternMatch; 46dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 4731ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumBlocksElim, "Number of blocks eliminated"); 4831ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumCmpUses, "Number of uses of Cmp expressions replaced with uses of " 4931ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich "sunken Cmps"); 5031ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumCastUses, "Number of uses of Cast expressions replaced with uses " 5131ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich "of sunken Casts"); 5231ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumMemoryInsts, "Number of memory instructions whose address " 5331ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich "computations were sunk"); 5431ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumExtsMoved, "Number of [s|z]ext instructions combined with loads"); 5531ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumExtUses, "Number of uses of [s|z]ext instructions optimized"); 567eb589d3f9294dbfe4d5205045bd8119a9666532Jakob Stoklund Olesen 57e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Chengstatic cl::opt<bool> 58e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan ChengCriticalEdgeSplit("cgp-critical-edge-splitting", 59e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng cl::desc("Split critical edges during codegen prepare"), 607eb589d3f9294dbfe4d5205045bd8119a9666532Jakob Stoklund Olesen cl::init(false), cl::Hidden); 61e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng 62692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christophernamespace { 633e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class CodeGenPrepare : public FunctionPass { 64dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// TLI - Keep a pointer of a TargetLowering to consult for determining 65dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// transformation profitability. 66dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner const TargetLowering *TLI; 6704149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng ProfileInfo *PFI; 68ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 69ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng /// BackEdges - Keep a set of all the loop back edges. 70ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng /// 71fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump SmallSet<std::pair<const BasicBlock*, const BasicBlock*>, 8> BackEdges; 72dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner public: 73ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 74c2bbfc18e9adbbdcf5b3375d8d25e2452f7df7f1Dan Gohman explicit CodeGenPrepare(const TargetLowering *tli = 0) 75081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson : FunctionPass(ID), TLI(tli) { 76081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeCodeGenPreparePass(*PassRegistry::getPassRegistry()); 77081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 78dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool runOnFunction(Function &F); 79692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 80ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter virtual void getAnalysisUsage(AnalysisUsage &AU) const { 81ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter AU.addPreserved<ProfileInfo>(); 82ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 83ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter 84aa0e52328747d982d6c6e501a205832ad724ff62Dan Gohman virtual void releaseMemory() { 85aa0e52328747d982d6c6e501a205832ad724ff62Dan Gohman BackEdges.clear(); 86aa0e52328747d982d6c6e501a205832ad724ff62Dan Gohman } 87aa0e52328747d982d6c6e501a205832ad724ff62Dan Gohman 88dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner private: 89d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool EliminateMostlyEmptyBlocks(Function &F); 90d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; 91d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner void EliminateMostlyEmptyBlock(BasicBlock *BB); 92dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool OptimizeBlock(BasicBlock &BB); 9388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner bool OptimizeMemoryInst(Instruction *I, Value *Addr, const Type *AccessTy, 9488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner DenseMap<Value*,Value*> &SunkAddrs); 959bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng bool OptimizeInlineAsmInst(Instruction *I, CallSite CS, 969bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng DenseMap<Value*,Value*> &SunkAddrs); 97040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher bool OptimizeCallInst(CallInst *CI); 98b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman bool MoveExtToFormExtLoad(Instruction *I); 99bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool OptimizeExtUses(Instruction *I); 100fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump void findLoopBackEdges(const Function &F); 101dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner }; 102dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 103794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 1041997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar CodeGenPrepare::ID = 0; 105d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(CodeGenPrepare, "codegenprepare", 106ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Optimize for code generation", false, false) 107dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 108dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris LattnerFunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { 109dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return new CodeGenPrepare(TLI); 110dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 111dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 112ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng/// findLoopBackEdges - Do a DFS walk to find loop back edges. 113ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng/// 114fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stumpvoid CodeGenPrepare::findLoopBackEdges(const Function &F) { 115fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges; 116fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump FindFunctionBackedges(F, Edges); 117fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump 118fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump BackEdges.insert(Edges.begin(), Edges.end()); 119ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng} 120ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 121dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 122dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::runOnFunction(Function &F) { 123dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool EverMadeChange = false; 124692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 12504149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI = getAnalysisIfAvailable<ProfileInfo>(); 126d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // First pass, eliminate blocks that contain only PHI nodes and an 127d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // unconditional branch. 128d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EverMadeChange |= EliminateMostlyEmptyBlocks(F); 129692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 13095bb00414eba82cc1c058b558cd28bc28134c561Cameron Zwarich // Now find loop back edges, but only if they are being used to decide which 13195bb00414eba82cc1c058b558cd28bc28134c561Cameron Zwarich // critical edges to split. 13295bb00414eba82cc1c058b558cd28bc28134c561Cameron Zwarich if (CriticalEdgeSplit) 13395bb00414eba82cc1c058b558cd28bc28134c561Cameron Zwarich findLoopBackEdges(F); 1347e66c0d43aefce78948f0b73422f6e5bb28e2077Evan Cheng 135d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = true; 136dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner while (MadeChange) { 137dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = false; 138dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 139dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange |= OptimizeBlock(*BB); 140dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner EverMadeChange |= MadeChange; 141dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 142dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return EverMadeChange; 143dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 144dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 1452d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes, 1462d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// debug info directives, and an unconditional branch. Passes before isel 1472d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// (e.g. LSR/loopsimplify) often split edges in ways that are non-optimal for 1482d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// isel. Start by eliminating these blocks so we can split them the way we 1492d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// want them. 150d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) { 151d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = false; 152d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Note that this intentionally skips the entry block. 153d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) { 154d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *BB = I++; 155d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 156d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If this block doesn't end with an uncond branch, ignore it. 157d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 158d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!BI || !BI->isUnconditional()) 159d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 160692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1612d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen // If the instruction before the branch (skipping debug info) isn't a phi 1622d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen // node, then other stuff is happening here. 163d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::iterator BBI = BI; 164d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBI != BB->begin()) { 165d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner --BBI; 1662d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen while (isa<DbgInfoIntrinsic>(BBI)) { 1672d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen if (BBI == BB->begin()) 1682d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen break; 1692d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen --BBI; 1702d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen } 1712d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI)) 1722d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen continue; 173d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 174692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 175d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Do not break infinite loops. 176d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 177d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (DestBB == BB) 178d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 179692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 180d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!CanMergeBlocks(BB, DestBB)) 181d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 182692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 183d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EliminateMostlyEmptyBlock(BB); 184d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner MadeChange = true; 185d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 186d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return MadeChange; 187d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 188d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 189d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a 190d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// single uncond branch between them, and BB contains no other non-phi 191d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// instructions. 192d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, 193d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const BasicBlock *DestBB) const { 194d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // We only want to eliminate blocks whose phi nodes are used by phi nodes in 195d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // the successor. If there are more complex condition (e.g. preheaders), 196d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // don't mess around with them. 197d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::const_iterator BBI = BB->begin(); 198d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 19960ad781c61815ca5b8dc2a45a102e1c8af65992fGabor Greif for (Value::const_use_iterator UI = PN->use_begin(), E = PN->use_end(); 200d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner UI != E; ++UI) { 201d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Instruction *User = cast<Instruction>(*UI); 202d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (User->getParent() != DestBB || !isa<PHINode>(User)) 203d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return false; 204692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If User is inside DestBB block and it is a PHINode then check 205692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // incoming value. If incoming value is not from BB then this is 20675abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel // a complex condition (e.g. preheaders) we want to avoid here. 20775abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (User->getParent() == DestBB) { 20875abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (const PHINode *UPN = dyn_cast<PHINode>(User)) 20975abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { 21075abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); 21175abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (Insn && Insn->getParent() == BB && 21275abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Insn->getParent() != UPN->getIncomingBlock(I)) 21375abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel return false; 21475abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 21575abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 216d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 217d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 218692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 219d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If BB and DestBB contain any common predecessors, then the phi nodes in BB 220d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // and DestBB may have conflicting incoming values for the block. If so, we 221d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // can't merge the block. 222d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); 223d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!DestBBPN) return true; // no conflict. 224692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 225d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Collect the preds of BB. 226f67f73a519eac94b6c1f98dbce7d251a3a4aea07Chris Lattner SmallPtrSet<const BasicBlock*, 16> BBPreds; 227d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 228d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // It is faster to get preds from a PHI than with pred_iterator. 229d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 230d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(BBPN->getIncomingBlock(i)); 231d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 232d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(pred_begin(BB), pred_end(BB)); 233d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 234692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 235d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Walk the preds of DestBB. 236d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { 237d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *Pred = DestBBPN->getIncomingBlock(i); 238d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBPreds.count(Pred)) { // Common predecessor? 239d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBI = DestBB->begin(); 240d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 241d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V1 = PN->getIncomingValueForBlock(Pred); 242d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V2 = PN->getIncomingValueForBlock(BB); 243692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 244d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If V2 is a phi node in BB, look up what the mapped value will be. 245d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) 246d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V2PN->getParent() == BB) 247d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner V2 = V2PN->getIncomingValueForBlock(Pred); 248692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 249d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If there is a conflict, bail out. 250d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V1 != V2) return false; 251d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 252d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 253d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 254d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 255d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return true; 256d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 257d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 258d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 259d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and 260d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// an unconditional branch in it. 261d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnervoid CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { 262d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 263d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 264692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 26568d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB); 266692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 267d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If the destination block has a single pred, then this is a trivial edge, 268d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // just collapse it. 2699918fb5631974f2201a640384b7ebe672c749e43Chris Lattner if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) { 270f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (SinglePred != DestBB) { 271f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // Remember if SinglePred was the entry block of the function. If so, we 272f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // will need to move BB back to the entry position. 273f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 274ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter MergeBasicBlockIntoOnlyPred(DestBB, this); 275f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 276f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (isEntry && BB != &BB->getParent()->getEntryBlock()) 277f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner BB->moveBefore(&BB->getParent()->getEntryBlock()); 278f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 27968d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 280f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner return; 281f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner } 282d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 283692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 284d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB 285d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // to handle the new incoming edges it is about to have. 286d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *PN; 287d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (BasicBlock::iterator BBI = DestBB->begin(); 288d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 289d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Remove the incoming value for BB, and remember it. 290d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner Value *InVal = PN->removeIncomingValue(BB, false); 291692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 292d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Two options: either the InVal is a phi node defined in BB or it is some 293d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // value that dominates BB. 294d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *InValPhi = dyn_cast<PHINode>(InVal); 295d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (InValPhi && InValPhi->getParent() == BB) { 296d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Add all of the input values of the input PHI as inputs of this phi. 297d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) 298d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InValPhi->getIncomingValue(i), 299d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner InValPhi->getIncomingBlock(i)); 300d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 301d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, add one instance of the dominating value for each edge that 302d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // we will be adding. 303d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 304d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 305d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); 306d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 307d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 308d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, *PI); 309d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 310d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 311d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 312692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 313d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // The PHIs are now updated, change everything that refers to BB to use 314d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // DestBB and remove BB. 315d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->replaceAllUsesWith(DestBB); 31604149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng if (PFI) { 31704149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI->replaceAllUses(BB, DestBB); 31804149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI->removeEdge(ProfileInfo::getEdge(BB, DestBB)); 319ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 320d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->eraseFromParent(); 32131ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumBlocksElim; 322692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 32368d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 324d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 325d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 32698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner/// FindReusablePredBB - Check all of the predecessors of the block DestPHI 32798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner/// lives in to see if there is a block that we can reuse as a critical edge 32898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner/// from TIBB. 32998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattnerstatic BasicBlock *FindReusablePredBB(PHINode *DestPHI, BasicBlock *TIBB) { 33098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner BasicBlock *Dest = DestPHI->getParent(); 33198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 33298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner /// TIPHIValues - This array is lazily computed to determine the values of 33398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner /// PHIs in Dest that TI would provide. 33498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner SmallVector<Value*, 32> TIPHIValues; 33598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 33698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner /// TIBBEntryNo - This is a cache to speed up pred queries for TIBB. 33798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner unsigned TIBBEntryNo = 0; 33898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 33998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // Check to see if Dest has any blocks that can be used as a split edge for 34098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // this terminator. 34198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner for (unsigned pi = 0, e = DestPHI->getNumIncomingValues(); pi != e; ++pi) { 34298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner BasicBlock *Pred = DestPHI->getIncomingBlock(pi); 34398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // To be usable, the pred has to end with an uncond branch to the dest. 34498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator()); 34598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (!PredBr || !PredBr->isUnconditional()) 34698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner continue; 34798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // Must be empty other than the branch and debug info. 34898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner BasicBlock::iterator I = Pred->begin(); 34998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner while (isa<DbgInfoIntrinsic>(I)) 35098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner I++; 35198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (&*I != PredBr) 35298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner continue; 35398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // Cannot be the entry block; its label does not get emitted. 35498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (Pred == &Dest->getParent()->getEntryBlock()) 35598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner continue; 35698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 35798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // Finally, since we know that Dest has phi nodes in it, we have to make 35898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // sure that jumping to Pred will have the same effect as going to Dest in 35998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // terms of PHI values. 36098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner PHINode *PN; 36198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner unsigned PHINo = 0; 36298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner unsigned PredEntryNo = pi; 36398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 36498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner bool FoundMatch = true; 36598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner for (BasicBlock::iterator I = Dest->begin(); 36698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) { 36798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (PHINo == TIPHIValues.size()) { 36898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (PN->getIncomingBlock(TIBBEntryNo) != TIBB) 36998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner TIBBEntryNo = PN->getBasicBlockIndex(TIBB); 37098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner TIPHIValues.push_back(PN->getIncomingValue(TIBBEntryNo)); 37198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner } 37298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 37398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // If the PHI entry doesn't work, we can't use this pred. 37498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (PN->getIncomingBlock(PredEntryNo) != Pred) 37598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner PredEntryNo = PN->getBasicBlockIndex(Pred); 37698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 37798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (TIPHIValues[PHINo] != PN->getIncomingValue(PredEntryNo)) { 37898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner FoundMatch = false; 37998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner break; 38098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner } 38198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner } 38298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 38398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // If we found a workable predecessor, change TI to branch to Succ. 38498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (FoundMatch) 38598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner return Pred; 38698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner } 38798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner return 0; 38898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner} 38998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 390d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 391ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner/// SplitEdgeNicely - Split the critical edge from TI to its specified 392dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// successor if it will improve codegen. We only do this if the successor has 393dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// phi nodes (otherwise critical edges are ok). If there is already another 394dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// predecessor of the succ that is empty (and thus has no phi nodes), use it 395dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// instead of introducing a new block. 396ab63152871f4144050d0a58d592a95e089fe40d4Evan Chengstatic void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, 397fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump SmallSet<std::pair<const BasicBlock*, 398fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump const BasicBlock*>, 8> &BackEdges, 399ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng Pass *P) { 400dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *TIBB = TI->getParent(); 401dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *Dest = TI->getSuccessor(SuccNum); 402dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner assert(isa<PHINode>(Dest->begin()) && 403dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner "This should only be called if Dest has a PHI!"); 4043f65b5e733e01faeb9db825515ca00e544fb988aChris Lattner PHINode *DestPHI = cast<PHINode>(Dest->begin()); 405692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 406fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng // Do not split edges to EH landing pads. 4073f65b5e733e01faeb9db825515ca00e544fb988aChris Lattner if (InvokeInst *Invoke = dyn_cast<InvokeInst>(TI)) 408fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng if (Invoke->getSuccessor(1) == Dest) 409fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng return; 410fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng 411ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner // As a hack, never split backedges of loops. Even though the copy for any 412ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner // PHIs inserted on the backedge would be dead for exits from the loop, we 413ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner // assume that the cost of *splitting* the backedge would be too high. 414ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng if (BackEdges.count(std::make_pair(TIBB, Dest))) 415ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner return; 416692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 417c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner if (BasicBlock *ReuseBB = FindReusablePredBB(DestPHI, TIBB)) { 418c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner ProfileInfo *PFI = P->getAnalysisIfAvailable<ProfileInfo>(); 419c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner if (PFI) 420c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner PFI->splitEdge(TIBB, Dest, ReuseBB); 421c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner Dest->removePredecessor(TIBB); 422c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner TI->setSuccessor(SuccNum, ReuseBB); 423ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng return; 424ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng } 425ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 426c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner SplitCriticalEdge(TI, SuccNum, P, true); 427dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 428dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 429ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 430dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// OptimizeNoopCopyExpression - If the specified cast instruction is a noop 431a119de86a064414622562cfe32953de7f9b0ee40Dan Gohman/// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC), 432a119de86a064414622562cfe32953de7f9b0ee40Dan Gohman/// sink it into user blocks to reduce the number of virtual 433ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// registers that must be created and coalesced. 434dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// 435dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// Return true if any changes are made. 43685fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner/// 437dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){ 438692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If this is a noop copy, 439e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 440e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT DstVT = TLI.getValueType(CI->getType()); 441692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 442dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This is an fp<->int conversion? 44383ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands if (SrcVT.isInteger() != DstVT.isInteger()) 444dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 4458e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands 446dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is an extension, it will be a zero or sign extension, which 447dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // isn't a noop. 4488e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands if (SrcVT.bitsLT(DstVT)) return false; 449692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 450dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If these values will be promoted, find out what they will be promoted 451dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // to. This helps us consider truncates on PPC as noop copies when they 452dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // are. 453aafe626c7fa9f99150cccd27d0151a2cf7c8c00bChris Lattner if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) 45423b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT); 455aafe626c7fa9f99150cccd27d0151a2cf7c8c00bChris Lattner if (TLI.getTypeAction(DstVT) == TargetLowering::Promote) 45623b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT); 457692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 458dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If, after promotion, these are the same types, this is a noop copy. 459dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SrcVT != DstVT) 460dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 461692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 462dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *DefBB = CI->getParent(); 463692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 464dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// InsertedCasts - Only insert a cast in each block once. 465ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CastInst*> InsertedCasts; 466692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 467dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 468692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 469dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner UI != E; ) { 470dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Use &TheUse = UI.getUse(); 471dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *User = cast<Instruction>(*UI); 472692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 473dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Figure out which BB this cast is used in. For PHI's this is the 474dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // appropriate predecessor block. 475dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *UserBB = User->getParent(); 476dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) { 477a36791da41cf4f635e50077b290676b873836bdaGabor Greif UserBB = PN->getIncomingBlock(UI); 478dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 479692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 480dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Preincrement use iterator so we don't invalidate it. 481dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner ++UI; 482692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 483dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If this user is in the same block as the cast, don't change the cast. 484dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (UserBB == DefBB) continue; 485692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 486dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we have already inserted a cast into this block, use it. 487dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CastInst *&InsertedCast = InsertedCasts[UserBB]; 488dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 489dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (!InsertedCast) { 49002dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 491692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 492692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCast = 493692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 494dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner InsertPt); 495dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = true; 496dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 497692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 498ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cast with a use of the new cast. 499dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TheUse = InsertedCast; 50031ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumCastUses; 501dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 502692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 503dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we removed all uses, nuke the cast. 504e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands if (CI->use_empty()) { 505dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CI->eraseFromParent(); 506e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands MadeChange = true; 507e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands } 508692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 509dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 510dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 511dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 512692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher/// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce 513ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// the number of virtual registers that must be created and coalesced. This is 514684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// a clear win except on targets with multiple condition code registers 515684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// (PowerPC), where it might lose; some adjustment may be wanted there. 516ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// 517ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// Return true if any changes are made. 51885fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattnerstatic bool OptimizeCmpExpression(CmpInst *CI) { 519ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *DefBB = CI->getParent(); 520692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 521ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen /// InsertedCmp - Only insert a cmp in each block once. 522ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CmpInst*> InsertedCmps; 523692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 524ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen bool MadeChange = false; 525692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 526ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen UI != E; ) { 527ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Use &TheUse = UI.getUse(); 528ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Instruction *User = cast<Instruction>(*UI); 529692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 530ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Preincrement use iterator so we don't invalidate it. 531ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen ++UI; 532692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 533ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Don't bother for PHI nodes. 534ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (isa<PHINode>(User)) 535ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen continue; 536ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 537ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Figure out which BB this cmp is used in. 538ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *UserBB = User->getParent(); 539692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 540ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If this user is in the same block as the cmp, don't change the cmp. 541ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (UserBB == DefBB) continue; 542692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 543ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we have already inserted a cmp into this block, use it. 544ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CmpInst *&InsertedCmp = InsertedCmps[UserBB]; 545ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 546ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (!InsertedCmp) { 54702dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 548692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 549692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCmp = 5501c8a23c440b1665ba422778cdc74a0c59ecaf39eDan Gohman CmpInst::Create(CI->getOpcode(), 551333c40096561218bc3597cf153c0a3895274414cOwen Anderson CI->getPredicate(), CI->getOperand(0), 552ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->getOperand(1), "", InsertPt); 553ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen MadeChange = true; 554ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 555692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 556ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cmp with a use of the new cmp. 557ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen TheUse = InsertedCmp; 55831ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumCmpUses; 559ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 560692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 561ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we removed all uses, nuke the cmp. 562ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (CI->use_empty()) 563ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->eraseFromParent(); 564692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 565ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen return MadeChange; 566ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen} 567ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 5680b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramernamespace { 5690b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramerclass CodeGenPrepareFortifiedLibCalls : public SimplifyFortifiedLibCalls { 5700b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramerprotected: 5710b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer void replaceCall(Value *With) { 5720b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CI->replaceAllUsesWith(With); 5730b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CI->eraseFromParent(); 5740b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer } 5750b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer bool isFoldable(unsigned SizeCIOp, unsigned, bool) const { 576a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif if (ConstantInt *SizeCI = 577a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) 578a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif return SizeCI->isAllOnesValue(); 5790b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer return false; 5800b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer } 5810b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer}; 5820b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer} // end anonymous namespace 5830b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer 584040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopherbool CodeGenPrepare::OptimizeCallInst(CallInst *CI) { 585040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // Lower all uses of llvm.objectsize.* 586040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI); 587040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (II && II->getIntrinsicID() == Intrinsic::objectsize) { 588de9f5452d3ae894bb7fdd455cec5af50e2560aa5Gabor Greif bool Min = (cast<ConstantInt>(II->getArgOperand(1))->getZExtValue() == 1); 589040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher const Type *ReturnTy = CI->getType(); 590040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL); 591040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher CI->replaceAllUsesWith(RetVal); 592040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher CI->eraseFromParent(); 593040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher return true; 594040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher } 595040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 596040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // From here on out we're working with named functions. 597040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (CI->getCalledFunction() == 0) return false; 598040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 599040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // We'll need TargetData from here on out. 600040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher const TargetData *TD = TLI ? TLI->getTargetData() : 0; 601040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (!TD) return false; 602040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 6030b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer // Lower all default uses of _chk calls. This is very similar 6040b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer // to what InstCombineCalls does, but here we are only lowering calls 605040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // that have the default "don't know" as the objectsize. Anything else 606040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // should be left alone. 6070b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CodeGenPrepareFortifiedLibCalls Simplifier; 6080b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer return Simplifier.fold(CI, TD); 609040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher} 61088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 61188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner// Memory Optimization 61288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 61388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 614dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// IsNonLocalValue - Return true if the specified values are defined in a 615dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// different basic block than BB. 616dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool IsNonLocalValue(Value *V, BasicBlock *BB) { 617dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 618dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return I->getParent() != BB; 619dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 620dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 621dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 6224a8ee23a8181f668dc294b417f67e1675ad391abBob Wilson/// OptimizeMemoryInst - Load and Store Instructions often have 623dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// addressing modes that can do significant amounts of computation. As such, 624dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// instruction selection will try to get the load or store to do as much 625dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// computation as possible for the program. The problem is that isel can only 626dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// see within a single block. As such, we sink as much legal addressing mode 627dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// stuff into the block as possible. 62888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// 62988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// This method is used to optimize both load/store and inline asms with memory 63088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// operands. 631896617b776e7b015346160645b19be776cbe3805Chris Lattnerbool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr, 63288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner const Type *AccessTy, 63388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner DenseMap<Value*,Value*> &SunkAddrs) { 63435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Value *Repl = Addr; 63535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 636d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson // Try to collapse single-value PHI nodes. This is necessary to undo 637d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson // unprofitable PRE transformations. 6387cb4fa20b5534decf527a6bfcc74bd79ea11cbb1Cameron Zwarich SmallVector<Value*, 8> worklist; 6397cb4fa20b5534decf527a6bfcc74bd79ea11cbb1Cameron Zwarich SmallPtrSet<Value*, 16> Visited; 64035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson worklist.push_back(Addr); 64135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 64235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // Use a worklist to iteratively look through PHI nodes, and ensure that 64335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // the addressing mode obtained from the non-PHI roots of the graph 64435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // are equivalent. 64535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Value *Consensus = 0; 64635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson unsigned NumUses = 0; 64735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson SmallVector<Instruction*, 16> AddrModeInsts; 64835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson ExtAddrMode AddrMode; 64935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson while (!worklist.empty()) { 65035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Value *V = worklist.back(); 65135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson worklist.pop_back(); 65235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 65335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // Break use-def graph loops. 65435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (Visited.count(V)) { 65535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Consensus = 0; 65635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson break; 65735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson } 65835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 65935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Visited.insert(V); 66035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 66135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // For a PHI node, push all of its incoming values. 66235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (PHINode *P = dyn_cast<PHINode>(V)) { 66335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) 66435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson worklist.push_back(P->getIncomingValue(i)); 66535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson continue; 66635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson } 66735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 66835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // For non-PHIs, determine the addressing mode being computed. 66935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson SmallVector<Instruction*, 16> NewAddrModeInsts; 67035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson ExtAddrMode NewAddrMode = 67135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson AddressingModeMatcher::Match(V, AccessTy,MemoryInst, 67235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson NewAddrModeInsts, *TLI); 67335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 67435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // Ensure that the obtained addressing mode is equivalent to that obtained 67535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // for all other roots of the PHI traversal. Also, when choosing one 67635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // such root as representative, select the one with the most uses in order 67735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // to keep the cost modeling heuristics in AddressingModeMatcher applicable. 67835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (!Consensus || NewAddrMode == AddrMode) { 67935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (V->getNumUses() > NumUses) { 68035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Consensus = V; 68135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson NumUses = V->getNumUses(); 68235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson AddrMode = NewAddrMode; 68335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson AddrModeInsts = NewAddrModeInsts; 684d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson } 68535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson continue; 686d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson } 687d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson 68835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Consensus = 0; 68935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson break; 690d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson } 691d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson 69235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // If the addressing mode couldn't be determined, or if multiple different 69335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // ones were determined, bail out now. 69435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (!Consensus) return false; 69535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 696dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if any of the instructions supersumed by this addr mode are 697dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // non-local to I's BB. 698dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool AnyNonLocal = false; 699dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { 700896617b776e7b015346160645b19be776cbe3805Chris Lattner if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) { 701dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AnyNonLocal = true; 702dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 703dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 704dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 705692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 706dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If all the instructions matched are already in this BB, don't do anything. 707dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!AnyNonLocal) { 70868d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: Found local addrmode: " << AddrMode << "\n"); 709dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 710dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 711692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 712dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Insert this computation right after this user. Since our caller is 713dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // scanning from the top of the BB to the bottom, reuse of the expr are 714dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // guaranteed to happen later. 715896617b776e7b015346160645b19be776cbe3805Chris Lattner BasicBlock::iterator InsertPt = MemoryInst; 716692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 717dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Now that we determined the addressing expression we want to use and know 718dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // that we have to sink it into this block. Check to see if we have already 719dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done this for some other load/store instr in this block. If so, reuse the 720dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // computation. 721dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *&SunkAddr = SunkAddrs[Addr]; 722dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr) { 72368d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for " 7246c1980b3357207c4d756255bc5e32323eac278dcDan Gohman << *MemoryInst); 725dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr->getType() != Addr->getType()) 726dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new BitCastInst(SunkAddr, Addr->getType(), "tmp", InsertPt); 727dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 72868d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for " 7296c1980b3357207c4d756255bc5e32323eac278dcDan Gohman << *MemoryInst); 7301d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson const Type *IntPtrTy = 7311d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson TLI->getTargetData()->getIntPtrType(AccessTy->getContext()); 732692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 733dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *Result = 0; 734d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman 735d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // Start with the base register. Do this first so that subsequent address 736d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // matching finds it last, which will prevent it from trying to match it 737d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // as the scaled value in case it happens to be a mul. That would be 738d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // problematic if we've sunk a different mul for the scale, because then 739d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // we'd end up sinking both muls. 740d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman if (AddrMode.BaseReg) { 741d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman Value *V = AddrMode.BaseReg; 7421df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (V->getType()->isPointerTy()) 743d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 744d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman if (V->getType() != IntPtrTy) 745d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman V = CastInst::CreateIntegerCast(V, IntPtrTy, /*isSigned=*/true, 746d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman "sunkaddr", InsertPt); 747d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman Result = V; 748d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman } 749d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman 750d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // Add the scale value. 751dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale) { 752dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = AddrMode.ScaledReg; 753dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (V->getType() == IntPtrTy) { 754dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done. 7551df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands } else if (V->getType()->isPointerTy()) { 756dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 757dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 758dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cast<IntegerType>(V->getType())->getBitWidth()) { 759dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new TruncInst(V, IntPtrTy, "sunkaddr", InsertPt); 760dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 761dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new SExtInst(V, IntPtrTy, "sunkaddr", InsertPt); 762dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 763dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale != 1) 764eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson V = BinaryOperator::CreateMul(V, ConstantInt::get(IntPtrTy, 765d672ecb0178c6247a5eaa5b0fb0c3b23cd25bd7cOwen Anderson AddrMode.Scale), 766dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner "sunkaddr", InsertPt); 767dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 7687cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 769dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 770dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 771dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 772692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 773dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the BaseGV if present. 774dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseGV) { 775dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = new PtrToIntInst(AddrMode.BaseGV, IntPtrTy, "sunkaddr", 776dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner InsertPt); 777dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 7787cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 779dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 780dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 781dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 782692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 783dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the Base Offset if present. 784dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseOffs) { 785eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 786dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 7877cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 788dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 789dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 790dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 791dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 792dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result == 0) 793a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson SunkAddr = Constant::getNullValue(Addr->getType()); 794dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 795dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new IntToPtrInst(Result, Addr->getType(), "sunkaddr",InsertPt); 796dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 797692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 798d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson MemoryInst->replaceUsesOfWith(Repl, SunkAddr); 799692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 800d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson if (Repl->use_empty()) { 801d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson RecursivelyDeleteTriviallyDeadInstructions(Repl); 802536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen // This address is now available for reassignment, so erase the table entry; 803536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen // we don't want to match some completely different instruction. 804536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen SunkAddrs[Addr] = 0; 805536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen } 80631ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumMemoryInsts; 807dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 808dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 809dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 8109bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// OptimizeInlineAsmInst - If there are any memory operands, use 81188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// OptimizeMemoryInst to sink their address computing into the block when 8129bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// possible / profitable. 8139bf12b5583104c810cfadcdce91edf9efad79973Evan Chengbool CodeGenPrepare::OptimizeInlineAsmInst(Instruction *I, CallSite CS, 8149bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng DenseMap<Value*,Value*> &SunkAddrs) { 8159bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng bool MadeChange = false; 8169bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 81744ab89eb376af838d1123293a79975aede501464John Thompson TargetLowering::AsmOperandInfoVector TargetConstraints = TLI->ParseConstraints(CS); 818677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen unsigned ArgNo = 0; 819eac6e1d0c748afc3d1496be0753ffbe5f5a4279bJohn Thompson for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) { 820eac6e1d0c748afc3d1496be0753ffbe5f5a4279bJohn Thompson TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i]; 821eac6e1d0c748afc3d1496be0753ffbe5f5a4279bJohn Thompson 8229bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Compute the constraint code and ConstraintType to use. 8231784d160e4efa75782884d451d0788b9457e67dcDale Johannesen TLI->ComputeConstraintToUse(OpInfo, SDValue()); 8249bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 8259ec8095485c994522c9a50e16fc029de94c20476Eli Friedman if (OpInfo.ConstraintType == TargetLowering::C_Memory && 8269ec8095485c994522c9a50e16fc029de94c20476Eli Friedman OpInfo.isIndirect) { 827677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen Value *OpVal = const_cast<Value *>(CS.getArgument(ArgNo++)); 82888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner MadeChange |= OptimizeMemoryInst(I, OpVal, OpVal->getType(), SunkAddrs); 829677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen } else if (OpInfo.Type == InlineAsm::isInput) 830677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen ArgNo++; 8319bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng } 8329bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 8339bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng return MadeChange; 8349bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng} 8359bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 836b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// MoveExtToFormExtLoad - Move a zext or sext fed by a load into the same 837b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// basic block as the load, unless conditions are unfavorable. This allows 838b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// SelectionDAG to fold the extend into the load. 839b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// 840b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohmanbool CodeGenPrepare::MoveExtToFormExtLoad(Instruction *I) { 841b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Look for a load being extended. 842b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LoadInst *LI = dyn_cast<LoadInst>(I->getOperand(0)); 843b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (!LI) return false; 844b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 845b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // If they're already in the same block, there's nothing to do. 846b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (LI->getParent() == I->getParent()) 847b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 848b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 849b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // If the load has other users and the truncate is not free, this probably 850b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // isn't worthwhile. 851b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (!LI->hasOneUse() && 852ec57a1acec7803fff2faa54c6ea8fec2be01aeb9Bob Wilson TLI && (TLI->isTypeLegal(TLI->getValueType(LI->getType())) || 853ec57a1acec7803fff2faa54c6ea8fec2be01aeb9Bob Wilson !TLI->isTypeLegal(TLI->getValueType(I->getType()))) && 85471dc4d96ed39fadcdccf8c578d49a1afdae0c6baBob Wilson !TLI->isTruncateFree(I->getType(), LI->getType())) 855b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 856b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 857b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Check whether the target supports casts folded into loads. 858b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman unsigned LType; 859b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (isa<ZExtInst>(I)) 860b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LType = ISD::ZEXTLOAD; 861b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman else { 862b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman assert(isa<SExtInst>(I) && "Unexpected ext type!"); 863b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LType = ISD::SEXTLOAD; 864b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman } 865b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (TLI && !TLI->isLoadExtLegal(LType, TLI->getValueType(LI->getType()))) 866b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 867b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 868b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Move the extend into the same block as the load, so that SelectionDAG 869b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // can fold it. 870b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman I->removeFromParent(); 871b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman I->insertAfter(LI); 87231ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumExtsMoved; 873b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return true; 874b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman} 875b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 876bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Chengbool CodeGenPrepare::OptimizeExtUses(Instruction *I) { 877bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *DefBB = I->getParent(); 878bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 8799120f5c35b756e0b9d7747616e97df8f30edfcc8Bob Wilson // If the result of a {s|z}ext and its source are both live out, rewrite all 880bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // other uses of the source with result of extension. 881bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Value *Src = I->getOperand(0); 882bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (Src->hasOneUse()) 883bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 884bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 885696e5c047bd06bf6b7b5471b3f4dec319b43628bEvan Cheng // Only do this xform if truncating is free. 88653bdbd756581a9a1d6d381059f103c5f3c687bb6Gabor Greif if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType())) 887f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng return false; 888f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng 889772de516b6851e679d3da9e5171712b9c3122019Evan Cheng // Only safe to perform the optimization if the source is also defined in 890765dff258545f019502023045b471443ff9ef6c4Evan Cheng // this block. 891765dff258545f019502023045b471443ff9ef6c4Evan Cheng if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent()) 892772de516b6851e679d3da9e5171712b9c3122019Evan Cheng return false; 893772de516b6851e679d3da9e5171712b9c3122019Evan Cheng 894bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool DefIsLiveOut = false; 895692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 896bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 897bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 898bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 899bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 900bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 901bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 902bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DefIsLiveOut = true; 903bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng break; 904bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 905bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!DefIsLiveOut) 906bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 907bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 908765dff258545f019502023045b471443ff9ef6c4Evan Cheng // Make sure non of the uses are PHI nodes. 909692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 910765dff258545f019502023045b471443ff9ef6c4Evan Cheng UI != E; ++UI) { 911765dff258545f019502023045b471443ff9ef6c4Evan Cheng Instruction *User = cast<Instruction>(*UI); 912f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng BasicBlock *UserBB = User->getParent(); 913f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (UserBB == DefBB) continue; 914f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // Be conservative. We don't want this xform to end up introducing 915f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // reloads just before load / store instructions. 916f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User)) 917765dff258545f019502023045b471443ff9ef6c4Evan Cheng return false; 918765dff258545f019502023045b471443ff9ef6c4Evan Cheng } 919765dff258545f019502023045b471443ff9ef6c4Evan Cheng 920bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // InsertedTruncs - Only insert one trunc in each block once. 921bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DenseMap<BasicBlock*, Instruction*> InsertedTruncs; 922bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 923bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool MadeChange = false; 924692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 925bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 926bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Use &TheUse = UI.getUse(); 927bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 928bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 929bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 930bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 931bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 932bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 933bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Both src and def are live in this block. Rewrite the use. 934bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *&InsertedTrunc = InsertedTruncs[UserBB]; 935bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 936bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!InsertedTrunc) { 93702dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 938692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 939bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt); 940bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 941bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 942bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Replace a use of the {s|z}ext source with a use of the result. 943bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng TheUse = InsertedTrunc; 94431ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumExtUses; 945bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange = true; 946bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 947bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 948bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return MadeChange; 949bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng} 950bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 951dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// In this pass we look for GEP and cast instructions that are used 952dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// across basic blocks and rewrite them to improve basic-block-at-a-time 953dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// selection. 954dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { 955dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 956692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 957ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng // Split all critical edges where the dest block has a PHI. 958e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng if (CriticalEdgeSplit) { 959e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng TerminatorInst *BBTI = BB.getTerminator(); 960e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng if (BBTI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(BBTI)) { 961e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng for (unsigned i = 0, e = BBTI->getNumSuccessors(); i != e; ++i) { 962e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng BasicBlock *SuccBB = BBTI->getSuccessor(i); 963e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng if (isa<PHINode>(SuccBB->begin()) && isCriticalEdge(BBTI, i, true)) 964e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng SplitEdgeNicely(BBTI, i, BackEdges, this); 965e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng } 966ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng } 967dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 968692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 969dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Keep track of non-local addresses that have been sunk into this block. 970dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This allows us to avoid inserting duplicate code for blocks with multiple 971dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // load/stores of the same address. 972dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DenseMap<Value*, Value*> SunkAddrs; 973692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 974dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (BasicBlock::iterator BBI = BB.begin(), E = BB.end(); BBI != E; ) { 975dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *I = BBI++; 976692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 977d5f8684b16057df73771b23e293b400cb327e079Owen Anderson if (PHINode *P = dyn_cast<PHINode>(I)) { 978d5f8684b16057df73771b23e293b400cb327e079Owen Anderson // It is possible for very late stage optimizations (such as SimplifyCFG) 979d5f8684b16057df73771b23e293b400cb327e079Owen Anderson // to introduce PHI nodes too late to be cleaned up. If we detect such a 980d5f8684b16057df73771b23e293b400cb327e079Owen Anderson // trivial PHI, go ahead and zap it here. 981d5f8684b16057df73771b23e293b400cb327e079Owen Anderson if (Value *V = SimplifyInstruction(P)) { 982d5f8684b16057df73771b23e293b400cb327e079Owen Anderson P->replaceAllUsesWith(V); 983d5f8684b16057df73771b23e293b400cb327e079Owen Anderson P->eraseFromParent(); 984d5f8684b16057df73771b23e293b400cb327e079Owen Anderson } 985d5f8684b16057df73771b23e293b400cb327e079Owen Anderson } else if (CastInst *CI = dyn_cast<CastInst>(I)) { 986dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If the source of the cast is a constant, then this should have 987dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // already been constant folded. The only reason NOT to constant fold 988dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // it is if something (e.g. LSR) was careful to place the constant 989dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // evaluation in a block other than then one that uses it (e.g. to hoist 990dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // the address of globals out of a loop). If this is the case, we don't 991dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // want to forward-subst the cast. 992dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (isa<Constant>(CI->getOperand(0))) 993dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner continue; 994692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 995bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool Change = false; 996bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (TLI) { 997bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Change = OptimizeNoopCopyExpression(CI, *TLI); 998bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange |= Change; 999bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 1000bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1001b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (!Change && (isa<ZExtInst>(I) || isa<SExtInst>(I))) { 1002b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman MadeChange |= MoveExtToFormExtLoad(I); 1003bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange |= OptimizeExtUses(I); 1004b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman } 1005ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } else if (CmpInst *CI = dyn_cast<CmpInst>(I)) { 1006ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen MadeChange |= OptimizeCmpExpression(CI); 1007dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 1008dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI) 100988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner MadeChange |= OptimizeMemoryInst(I, I->getOperand(0), LI->getType(), 101088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner SunkAddrs); 1011dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 1012dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI) 101388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner MadeChange |= OptimizeMemoryInst(I, SI->getOperand(1), 101488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner SI->getOperand(0)->getType(), 101588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner SunkAddrs); 1016dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 1017f25646bfb375b614cddcc8b6fda2b524feae1efaChris Lattner if (GEPI->hasAllZeroIndices()) { 1018dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner /// The GEP operand must be a pointer, so must its result -> BitCast 1019692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 1020dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->getName(), GEPI); 1021dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->replaceAllUsesWith(NC); 1022dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->eraseFromParent(); 1023dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner MadeChange = true; 1024dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner BBI = NC; 1025dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 1026dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (CallInst *CI = dyn_cast<CallInst>(I)) { 1027dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If we found an inline asm expession, and if the target knows how to 1028dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // lower it to normal LLVM code, do so now. 10298850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner if (TLI && isa<InlineAsm>(CI->getCalledValue())) { 10308850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner if (TLI->ExpandInlineAsm(CI)) { 10318850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner BBI = BB.begin(); 10328850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner // Avoid processing instructions out of order, which could cause 10338850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner // reuse before a value is defined. 10348850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner SunkAddrs.clear(); 10358850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner } else 10368850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner // Sink address computing for memory operands into the block. 10378850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner MadeChange |= OptimizeInlineAsmInst(I, &(*CI), SunkAddrs); 1038040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher } else { 1039040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // Other CallInst optimizations that don't need to muck with the 1040040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // enclosing iterator here. 1041040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher MadeChange |= OptimizeCallInst(CI); 10428850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner } 1043dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 1044dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 1045692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1046dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 1047dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 1048