CodeGenPrepare.cpp revision 536d31b5b391ee76eae33f4756f6442bf10b2d72
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" 25ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter#include "llvm/Analysis/ProfileInfo.h" 26dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetData.h" 27dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetLowering.h" 28a1fd5b386dd8eb4c86bfd2b9659c219a1c4f56dbEvan Cheng#include "llvm/Transforms/Utils/AddrModeMatcher.h" 29dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 30dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Transforms/Utils/Local.h" 31040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher#include "llvm/Transforms/Utils/BuildLibCalls.h" 32dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/ADT/DenseMap.h" 33dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/ADT/SmallSet.h" 3403ce042d70c423a41edca0714112a0e06b16493bDan Gohman#include "llvm/Assembly/Writer.h" 359bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng#include "llvm/Support/CallSite.h" 36bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng#include "llvm/Support/Debug.h" 37dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 38088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner#include "llvm/Support/PatternMatch.h" 396c1980b3357207c4d756255bc5e32323eac278dcDan Gohman#include "llvm/Support/raw_ostream.h" 40040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher#include "llvm/Support/IRBuilder.h" 41dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerusing namespace llvm; 42088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattnerusing namespace llvm::PatternMatch; 43dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 44692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christophernamespace { 453e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class CodeGenPrepare : public FunctionPass { 46dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// TLI - Keep a pointer of a TargetLowering to consult for determining 47dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// transformation profitability. 48dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner const TargetLowering *TLI; 4904149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng ProfileInfo *PFI; 50ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 51ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng /// BackEdges - Keep a set of all the loop back edges. 52ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng /// 53fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump SmallSet<std::pair<const BasicBlock*, const BasicBlock*>, 8> BackEdges; 54dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner public: 55ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 56c2bbfc18e9adbbdcf5b3375d8d25e2452f7df7f1Dan Gohman explicit CodeGenPrepare(const TargetLowering *tli = 0) 57ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman : FunctionPass(&ID), TLI(tli) {} 58dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool runOnFunction(Function &F); 59692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 60ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter virtual void getAnalysisUsage(AnalysisUsage &AU) const { 61ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter AU.addPreserved<ProfileInfo>(); 62ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 63ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter 64aa0e52328747d982d6c6e501a205832ad724ff62Dan Gohman virtual void releaseMemory() { 65aa0e52328747d982d6c6e501a205832ad724ff62Dan Gohman BackEdges.clear(); 66aa0e52328747d982d6c6e501a205832ad724ff62Dan Gohman } 67aa0e52328747d982d6c6e501a205832ad724ff62Dan Gohman 68dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner private: 69d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool EliminateMostlyEmptyBlocks(Function &F); 70d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; 71d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner void EliminateMostlyEmptyBlock(BasicBlock *BB); 72dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool OptimizeBlock(BasicBlock &BB); 7388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner bool OptimizeMemoryInst(Instruction *I, Value *Addr, const Type *AccessTy, 7488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner DenseMap<Value*,Value*> &SunkAddrs); 759bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng bool OptimizeInlineAsmInst(Instruction *I, CallSite CS, 769bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng DenseMap<Value*,Value*> &SunkAddrs); 77040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher bool OptimizeCallInst(CallInst *CI); 78b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman bool MoveExtToFormExtLoad(Instruction *I); 79bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool OptimizeExtUses(Instruction *I); 80fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump void findLoopBackEdges(const Function &F); 81dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner }; 82dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 83794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 841997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar CodeGenPrepare::ID = 0; 85dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerstatic RegisterPass<CodeGenPrepare> X("codegenprepare", 86dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner "Optimize for code generation"); 87dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 88dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris LattnerFunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { 89dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return new CodeGenPrepare(TLI); 90dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 91dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 92ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng/// findLoopBackEdges - Do a DFS walk to find loop back edges. 93ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng/// 94fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stumpvoid CodeGenPrepare::findLoopBackEdges(const Function &F) { 95fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges; 96fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump FindFunctionBackedges(F, Edges); 97fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump 98fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump BackEdges.insert(Edges.begin(), Edges.end()); 99ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng} 100ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 101dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 102dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::runOnFunction(Function &F) { 103dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool EverMadeChange = false; 104692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 10504149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI = getAnalysisIfAvailable<ProfileInfo>(); 106d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // First pass, eliminate blocks that contain only PHI nodes and an 107d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // unconditional branch. 108d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EverMadeChange |= EliminateMostlyEmptyBlocks(F); 109692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1107e66c0d43aefce78948f0b73422f6e5bb28e2077Evan Cheng // Now find loop back edges. 1117e66c0d43aefce78948f0b73422f6e5bb28e2077Evan Cheng findLoopBackEdges(F); 1127e66c0d43aefce78948f0b73422f6e5bb28e2077Evan Cheng 113d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = true; 114dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner while (MadeChange) { 115dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = false; 116dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 117dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange |= OptimizeBlock(*BB); 118dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner EverMadeChange |= MadeChange; 119dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 120dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return EverMadeChange; 121dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 122dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 1232d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes, 1242d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// debug info directives, and an unconditional branch. Passes before isel 1252d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// (e.g. LSR/loopsimplify) often split edges in ways that are non-optimal for 1262d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// isel. Start by eliminating these blocks so we can split them the way we 1272d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// want them. 128d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) { 129d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = false; 130d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Note that this intentionally skips the entry block. 131d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) { 132d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *BB = I++; 133d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 134d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If this block doesn't end with an uncond branch, ignore it. 135d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 136d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!BI || !BI->isUnconditional()) 137d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 138692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1392d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen // If the instruction before the branch (skipping debug info) isn't a phi 1402d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen // node, then other stuff is happening here. 141d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::iterator BBI = BI; 142d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBI != BB->begin()) { 143d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner --BBI; 1442d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen while (isa<DbgInfoIntrinsic>(BBI)) { 1452d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen if (BBI == BB->begin()) 1462d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen break; 1472d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen --BBI; 1482d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen } 1492d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI)) 1502d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen continue; 151d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 152692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 153d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Do not break infinite loops. 154d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 155d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (DestBB == BB) 156d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 157692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 158d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!CanMergeBlocks(BB, DestBB)) 159d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 160692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 161d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EliminateMostlyEmptyBlock(BB); 162d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner MadeChange = true; 163d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 164d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return MadeChange; 165d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 166d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 167d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a 168d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// single uncond branch between them, and BB contains no other non-phi 169d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// instructions. 170d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, 171d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const BasicBlock *DestBB) const { 172d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // We only want to eliminate blocks whose phi nodes are used by phi nodes in 173d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // the successor. If there are more complex condition (e.g. preheaders), 174d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // don't mess around with them. 175d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::const_iterator BBI = BB->begin(); 176d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 17760ad781c61815ca5b8dc2a45a102e1c8af65992fGabor Greif for (Value::const_use_iterator UI = PN->use_begin(), E = PN->use_end(); 178d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner UI != E; ++UI) { 179d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Instruction *User = cast<Instruction>(*UI); 180d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (User->getParent() != DestBB || !isa<PHINode>(User)) 181d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return false; 182692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If User is inside DestBB block and it is a PHINode then check 183692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // incoming value. If incoming value is not from BB then this is 18475abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel // a complex condition (e.g. preheaders) we want to avoid here. 18575abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (User->getParent() == DestBB) { 18675abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (const PHINode *UPN = dyn_cast<PHINode>(User)) 18775abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { 18875abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); 18975abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (Insn && Insn->getParent() == BB && 19075abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Insn->getParent() != UPN->getIncomingBlock(I)) 19175abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel return false; 19275abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 19375abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 194d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 195d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 196692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 197d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If BB and DestBB contain any common predecessors, then the phi nodes in BB 198d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // and DestBB may have conflicting incoming values for the block. If so, we 199d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // can't merge the block. 200d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); 201d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!DestBBPN) return true; // no conflict. 202692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 203d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Collect the preds of BB. 204f67f73a519eac94b6c1f98dbce7d251a3a4aea07Chris Lattner SmallPtrSet<const BasicBlock*, 16> BBPreds; 205d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 206d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // It is faster to get preds from a PHI than with pred_iterator. 207d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 208d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(BBPN->getIncomingBlock(i)); 209d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 210d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(pred_begin(BB), pred_end(BB)); 211d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 212692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 213d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Walk the preds of DestBB. 214d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { 215d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *Pred = DestBBPN->getIncomingBlock(i); 216d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBPreds.count(Pred)) { // Common predecessor? 217d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBI = DestBB->begin(); 218d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 219d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V1 = PN->getIncomingValueForBlock(Pred); 220d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V2 = PN->getIncomingValueForBlock(BB); 221692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 222d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If V2 is a phi node in BB, look up what the mapped value will be. 223d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) 224d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V2PN->getParent() == BB) 225d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner V2 = V2PN->getIncomingValueForBlock(Pred); 226692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 227d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If there is a conflict, bail out. 228d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V1 != V2) return false; 229d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 230d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 231d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 232d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 233d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return true; 234d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 235d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 236d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 237d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and 238d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// an unconditional branch in it. 239d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnervoid CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { 240d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 241d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 242692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 24368d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB); 244692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 245d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If the destination block has a single pred, then this is a trivial edge, 246d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // just collapse it. 2479918fb5631974f2201a640384b7ebe672c749e43Chris Lattner if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) { 248f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (SinglePred != DestBB) { 249f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // Remember if SinglePred was the entry block of the function. If so, we 250f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // will need to move BB back to the entry position. 251f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 252ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter MergeBasicBlockIntoOnlyPred(DestBB, this); 253f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 254f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (isEntry && BB != &BB->getParent()->getEntryBlock()) 255f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner BB->moveBefore(&BB->getParent()->getEntryBlock()); 256f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 25768d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 258f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner return; 259f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner } 260d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 261692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 262d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB 263d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // to handle the new incoming edges it is about to have. 264d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *PN; 265d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (BasicBlock::iterator BBI = DestBB->begin(); 266d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 267d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Remove the incoming value for BB, and remember it. 268d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner Value *InVal = PN->removeIncomingValue(BB, false); 269692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 270d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Two options: either the InVal is a phi node defined in BB or it is some 271d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // value that dominates BB. 272d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *InValPhi = dyn_cast<PHINode>(InVal); 273d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (InValPhi && InValPhi->getParent() == BB) { 274d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Add all of the input values of the input PHI as inputs of this phi. 275d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) 276d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InValPhi->getIncomingValue(i), 277d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner InValPhi->getIncomingBlock(i)); 278d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 279d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, add one instance of the dominating value for each edge that 280d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // we will be adding. 281d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 282d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 283d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); 284d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 285d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 286d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, *PI); 287d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 288d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 289d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 290692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 291d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // The PHIs are now updated, change everything that refers to BB to use 292d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // DestBB and remove BB. 293d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->replaceAllUsesWith(DestBB); 29404149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng if (PFI) { 29504149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI->replaceAllUses(BB, DestBB); 29604149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI->removeEdge(ProfileInfo::getEdge(BB, DestBB)); 297ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 298d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->eraseFromParent(); 299692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 30068d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 301d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 302d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 30398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner/// FindReusablePredBB - Check all of the predecessors of the block DestPHI 30498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner/// lives in to see if there is a block that we can reuse as a critical edge 30598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner/// from TIBB. 30698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattnerstatic BasicBlock *FindReusablePredBB(PHINode *DestPHI, BasicBlock *TIBB) { 30798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner BasicBlock *Dest = DestPHI->getParent(); 30898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 30998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner /// TIPHIValues - This array is lazily computed to determine the values of 31098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner /// PHIs in Dest that TI would provide. 31198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner SmallVector<Value*, 32> TIPHIValues; 31298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 31398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner /// TIBBEntryNo - This is a cache to speed up pred queries for TIBB. 31498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner unsigned TIBBEntryNo = 0; 31598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 31698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // Check to see if Dest has any blocks that can be used as a split edge for 31798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // this terminator. 31898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner for (unsigned pi = 0, e = DestPHI->getNumIncomingValues(); pi != e; ++pi) { 31998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner BasicBlock *Pred = DestPHI->getIncomingBlock(pi); 32098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // To be usable, the pred has to end with an uncond branch to the dest. 32198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator()); 32298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (!PredBr || !PredBr->isUnconditional()) 32398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner continue; 32498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // Must be empty other than the branch and debug info. 32598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner BasicBlock::iterator I = Pred->begin(); 32698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner while (isa<DbgInfoIntrinsic>(I)) 32798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner I++; 32898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (&*I != PredBr) 32998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner continue; 33098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // Cannot be the entry block; its label does not get emitted. 33198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (Pred == &Dest->getParent()->getEntryBlock()) 33298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner continue; 33398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 33498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // Finally, since we know that Dest has phi nodes in it, we have to make 33598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // sure that jumping to Pred will have the same effect as going to Dest in 33698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // terms of PHI values. 33798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner PHINode *PN; 33898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner unsigned PHINo = 0; 33998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner unsigned PredEntryNo = pi; 34098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 34198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner bool FoundMatch = true; 34298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner for (BasicBlock::iterator I = Dest->begin(); 34398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) { 34498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (PHINo == TIPHIValues.size()) { 34598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (PN->getIncomingBlock(TIBBEntryNo) != TIBB) 34698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner TIBBEntryNo = PN->getBasicBlockIndex(TIBB); 34798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner TIPHIValues.push_back(PN->getIncomingValue(TIBBEntryNo)); 34898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner } 34998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 35098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // If the PHI entry doesn't work, we can't use this pred. 35198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (PN->getIncomingBlock(PredEntryNo) != Pred) 35298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner PredEntryNo = PN->getBasicBlockIndex(Pred); 35398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 35498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (TIPHIValues[PHINo] != PN->getIncomingValue(PredEntryNo)) { 35598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner FoundMatch = false; 35698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner break; 35798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner } 35898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner } 35998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 36098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // If we found a workable predecessor, change TI to branch to Succ. 36198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (FoundMatch) 36298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner return Pred; 36398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner } 36498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner return 0; 36598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner} 36698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 367d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 368ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner/// SplitEdgeNicely - Split the critical edge from TI to its specified 369dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// successor if it will improve codegen. We only do this if the successor has 370dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// phi nodes (otherwise critical edges are ok). If there is already another 371dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// predecessor of the succ that is empty (and thus has no phi nodes), use it 372dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// instead of introducing a new block. 373ab63152871f4144050d0a58d592a95e089fe40d4Evan Chengstatic void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, 374fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump SmallSet<std::pair<const BasicBlock*, 375fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump const BasicBlock*>, 8> &BackEdges, 376ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng Pass *P) { 377dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *TIBB = TI->getParent(); 378dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *Dest = TI->getSuccessor(SuccNum); 379dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner assert(isa<PHINode>(Dest->begin()) && 380dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner "This should only be called if Dest has a PHI!"); 3813f65b5e733e01faeb9db825515ca00e544fb988aChris Lattner PHINode *DestPHI = cast<PHINode>(Dest->begin()); 382692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 383fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng // Do not split edges to EH landing pads. 3843f65b5e733e01faeb9db825515ca00e544fb988aChris Lattner if (InvokeInst *Invoke = dyn_cast<InvokeInst>(TI)) 385fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng if (Invoke->getSuccessor(1) == Dest) 386fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng return; 387fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng 388ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner // As a hack, never split backedges of loops. Even though the copy for any 389ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner // PHIs inserted on the backedge would be dead for exits from the loop, we 390ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner // assume that the cost of *splitting* the backedge would be too high. 391ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng if (BackEdges.count(std::make_pair(TIBB, Dest))) 392ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner return; 393692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 394c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner if (BasicBlock *ReuseBB = FindReusablePredBB(DestPHI, TIBB)) { 395c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner ProfileInfo *PFI = P->getAnalysisIfAvailable<ProfileInfo>(); 396c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner if (PFI) 397c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner PFI->splitEdge(TIBB, Dest, ReuseBB); 398c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner Dest->removePredecessor(TIBB); 399c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner TI->setSuccessor(SuccNum, ReuseBB); 400ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng return; 401ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng } 402ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 403c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner SplitCriticalEdge(TI, SuccNum, P, true); 404dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 405dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 406ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 407dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// OptimizeNoopCopyExpression - If the specified cast instruction is a noop 408a119de86a064414622562cfe32953de7f9b0ee40Dan Gohman/// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC), 409a119de86a064414622562cfe32953de7f9b0ee40Dan Gohman/// sink it into user blocks to reduce the number of virtual 410ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// registers that must be created and coalesced. 411dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// 412dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// Return true if any changes are made. 41385fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner/// 414dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){ 415692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If this is a noop copy, 416e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 417e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT DstVT = TLI.getValueType(CI->getType()); 418692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 419dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This is an fp<->int conversion? 42083ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands if (SrcVT.isInteger() != DstVT.isInteger()) 421dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 4228e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands 423dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is an extension, it will be a zero or sign extension, which 424dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // isn't a noop. 4258e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands if (SrcVT.bitsLT(DstVT)) return false; 426692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 427dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If these values will be promoted, find out what they will be promoted 428dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // to. This helps us consider truncates on PPC as noop copies when they 429dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // are. 43023b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson if (TLI.getTypeAction(CI->getContext(), SrcVT) == TargetLowering::Promote) 43123b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT); 43223b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson if (TLI.getTypeAction(CI->getContext(), DstVT) == TargetLowering::Promote) 43323b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT); 434692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 435dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If, after promotion, these are the same types, this is a noop copy. 436dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SrcVT != DstVT) 437dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 438692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 439dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *DefBB = CI->getParent(); 440692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 441dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// InsertedCasts - Only insert a cast in each block once. 442ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CastInst*> InsertedCasts; 443692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 444dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 445692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 446dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner UI != E; ) { 447dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Use &TheUse = UI.getUse(); 448dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *User = cast<Instruction>(*UI); 449692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 450dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Figure out which BB this cast is used in. For PHI's this is the 451dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // appropriate predecessor block. 452dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *UserBB = User->getParent(); 453dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) { 454a36791da41cf4f635e50077b290676b873836bdaGabor Greif UserBB = PN->getIncomingBlock(UI); 455dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 456692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 457dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Preincrement use iterator so we don't invalidate it. 458dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner ++UI; 459692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 460dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If this user is in the same block as the cast, don't change the cast. 461dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (UserBB == DefBB) continue; 462692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 463dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we have already inserted a cast into this block, use it. 464dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CastInst *&InsertedCast = InsertedCasts[UserBB]; 465dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 466dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (!InsertedCast) { 46702dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 468692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 469692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCast = 470692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 471dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner InsertPt); 472dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = true; 473dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 474692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 475ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cast with a use of the new cast. 476dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TheUse = InsertedCast; 477dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 478692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 479dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we removed all uses, nuke the cast. 480e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands if (CI->use_empty()) { 481dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CI->eraseFromParent(); 482e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands MadeChange = true; 483e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands } 484692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 485dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 486dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 487dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 488692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher/// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce 489ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// the number of virtual registers that must be created and coalesced. This is 490684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// a clear win except on targets with multiple condition code registers 491684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// (PowerPC), where it might lose; some adjustment may be wanted there. 492ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// 493ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// Return true if any changes are made. 49485fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattnerstatic bool OptimizeCmpExpression(CmpInst *CI) { 495ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *DefBB = CI->getParent(); 496692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 497ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen /// InsertedCmp - Only insert a cmp in each block once. 498ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CmpInst*> InsertedCmps; 499692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 500ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen bool MadeChange = false; 501692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 502ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen UI != E; ) { 503ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Use &TheUse = UI.getUse(); 504ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Instruction *User = cast<Instruction>(*UI); 505692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 506ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Preincrement use iterator so we don't invalidate it. 507ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen ++UI; 508692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 509ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Don't bother for PHI nodes. 510ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (isa<PHINode>(User)) 511ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen continue; 512ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 513ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Figure out which BB this cmp is used in. 514ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *UserBB = User->getParent(); 515692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 516ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If this user is in the same block as the cmp, don't change the cmp. 517ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (UserBB == DefBB) continue; 518692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 519ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we have already inserted a cmp into this block, use it. 520ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CmpInst *&InsertedCmp = InsertedCmps[UserBB]; 521ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 522ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (!InsertedCmp) { 52302dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 524692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 525692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCmp = 5261c8a23c440b1665ba422778cdc74a0c59ecaf39eDan Gohman CmpInst::Create(CI->getOpcode(), 527333c40096561218bc3597cf153c0a3895274414cOwen Anderson CI->getPredicate(), CI->getOperand(0), 528ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->getOperand(1), "", InsertPt); 529ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen MadeChange = true; 530ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 531692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 532ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cmp with a use of the new cmp. 533ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen TheUse = InsertedCmp; 534ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 535692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 536ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we removed all uses, nuke the cmp. 537ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (CI->use_empty()) 538ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->eraseFromParent(); 539692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 540ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen return MadeChange; 541ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen} 542ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 5430b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramernamespace { 5440b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramerclass CodeGenPrepareFortifiedLibCalls : public SimplifyFortifiedLibCalls { 5450b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramerprotected: 5460b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer void replaceCall(Value *With) { 5470b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CI->replaceAllUsesWith(With); 5480b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CI->eraseFromParent(); 5490b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer } 5500b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer bool isFoldable(unsigned SizeCIOp, unsigned, bool) const { 5510b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer if (ConstantInt *SizeCI = dyn_cast<ConstantInt>(CI->getOperand(SizeCIOp))) 5520b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer return SizeCI->isAllOnesValue(); 5530b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer return false; 5540b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer } 5550b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer}; 5560b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer} // end anonymous namespace 5570b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer 558040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopherbool CodeGenPrepare::OptimizeCallInst(CallInst *CI) { 559040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // Lower all uses of llvm.objectsize.* 560040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI); 561040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (II && II->getIntrinsicID() == Intrinsic::objectsize) { 562040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher bool Min = (cast<ConstantInt>(II->getOperand(2))->getZExtValue() == 1); 563040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher const Type *ReturnTy = CI->getType(); 564040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL); 565040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher CI->replaceAllUsesWith(RetVal); 566040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher CI->eraseFromParent(); 567040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher return true; 568040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher } 569040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 570040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // From here on out we're working with named functions. 571040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (CI->getCalledFunction() == 0) return false; 572040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 573040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // We'll need TargetData from here on out. 574040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher const TargetData *TD = TLI ? TLI->getTargetData() : 0; 575040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (!TD) return false; 576040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 5770b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer // Lower all default uses of _chk calls. This is very similar 5780b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer // to what InstCombineCalls does, but here we are only lowering calls 579040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // that have the default "don't know" as the objectsize. Anything else 580040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // should be left alone. 5810b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CodeGenPrepareFortifiedLibCalls Simplifier; 5820b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer return Simplifier.fold(CI, TD); 583040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher} 58488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 58588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner// Memory Optimization 58688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 58788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 588dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// IsNonLocalValue - Return true if the specified values are defined in a 589dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// different basic block than BB. 590dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool IsNonLocalValue(Value *V, BasicBlock *BB) { 591dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 592dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return I->getParent() != BB; 593dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 594dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 595dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 5964a8ee23a8181f668dc294b417f67e1675ad391abBob Wilson/// OptimizeMemoryInst - Load and Store Instructions often have 597dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// addressing modes that can do significant amounts of computation. As such, 598dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// instruction selection will try to get the load or store to do as much 599dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// computation as possible for the program. The problem is that isel can only 600dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// see within a single block. As such, we sink as much legal addressing mode 601dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// stuff into the block as possible. 60288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// 60388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// This method is used to optimize both load/store and inline asms with memory 60488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// operands. 605896617b776e7b015346160645b19be776cbe3805Chris Lattnerbool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr, 60688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner const Type *AccessTy, 60788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner DenseMap<Value*,Value*> &SunkAddrs) { 608dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Figure out what addressing mode will be built up for this operation. 609dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SmallVector<Instruction*, 16> AddrModeInsts; 610896617b776e7b015346160645b19be776cbe3805Chris Lattner ExtAddrMode AddrMode = AddressingModeMatcher::Match(Addr, AccessTy,MemoryInst, 611896617b776e7b015346160645b19be776cbe3805Chris Lattner AddrModeInsts, *TLI); 612692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 613dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if any of the instructions supersumed by this addr mode are 614dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // non-local to I's BB. 615dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool AnyNonLocal = false; 616dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { 617896617b776e7b015346160645b19be776cbe3805Chris Lattner if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) { 618dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AnyNonLocal = true; 619dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 620dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 621dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 622692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 623dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If all the instructions matched are already in this BB, don't do anything. 624dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!AnyNonLocal) { 62568d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: Found local addrmode: " << AddrMode << "\n"); 626dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 627dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 628692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 629dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Insert this computation right after this user. Since our caller is 630dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // scanning from the top of the BB to the bottom, reuse of the expr are 631dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // guaranteed to happen later. 632896617b776e7b015346160645b19be776cbe3805Chris Lattner BasicBlock::iterator InsertPt = MemoryInst; 633692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 634dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Now that we determined the addressing expression we want to use and know 635dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // that we have to sink it into this block. Check to see if we have already 636dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done this for some other load/store instr in this block. If so, reuse the 637dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // computation. 638dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *&SunkAddr = SunkAddrs[Addr]; 639dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr) { 64068d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for " 6416c1980b3357207c4d756255bc5e32323eac278dcDan Gohman << *MemoryInst); 642dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr->getType() != Addr->getType()) 643dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new BitCastInst(SunkAddr, Addr->getType(), "tmp", InsertPt); 644dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 64568d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for " 6466c1980b3357207c4d756255bc5e32323eac278dcDan Gohman << *MemoryInst); 6471d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson const Type *IntPtrTy = 6481d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson TLI->getTargetData()->getIntPtrType(AccessTy->getContext()); 649692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 650dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *Result = 0; 651d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman 652d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // Start with the base register. Do this first so that subsequent address 653d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // matching finds it last, which will prevent it from trying to match it 654d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // as the scaled value in case it happens to be a mul. That would be 655d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // problematic if we've sunk a different mul for the scale, because then 656d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // we'd end up sinking both muls. 657d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman if (AddrMode.BaseReg) { 658d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman Value *V = AddrMode.BaseReg; 6591df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (V->getType()->isPointerTy()) 660d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 661d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman if (V->getType() != IntPtrTy) 662d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman V = CastInst::CreateIntegerCast(V, IntPtrTy, /*isSigned=*/true, 663d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman "sunkaddr", InsertPt); 664d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman Result = V; 665d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman } 666d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman 667d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // Add the scale value. 668dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale) { 669dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = AddrMode.ScaledReg; 670dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (V->getType() == IntPtrTy) { 671dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done. 6721df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands } else if (V->getType()->isPointerTy()) { 673dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 674dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 675dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cast<IntegerType>(V->getType())->getBitWidth()) { 676dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new TruncInst(V, IntPtrTy, "sunkaddr", InsertPt); 677dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 678dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new SExtInst(V, IntPtrTy, "sunkaddr", InsertPt); 679dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 680dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale != 1) 681eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson V = BinaryOperator::CreateMul(V, ConstantInt::get(IntPtrTy, 682d672ecb0178c6247a5eaa5b0fb0c3b23cd25bd7cOwen Anderson AddrMode.Scale), 683dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner "sunkaddr", InsertPt); 684dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 6857cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 686dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 687dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 688dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 689692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 690dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the BaseGV if present. 691dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseGV) { 692dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = new PtrToIntInst(AddrMode.BaseGV, IntPtrTy, "sunkaddr", 693dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner InsertPt); 694dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 6957cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 696dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 697dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 698dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 699692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 700dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the Base Offset if present. 701dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseOffs) { 702eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 703dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 7047cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 705dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 706dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 707dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 708dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 709dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result == 0) 710a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson SunkAddr = Constant::getNullValue(Addr->getType()); 711dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 712dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new IntToPtrInst(Result, Addr->getType(), "sunkaddr",InsertPt); 713dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 714692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 715896617b776e7b015346160645b19be776cbe3805Chris Lattner MemoryInst->replaceUsesOfWith(Addr, SunkAddr); 716692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 717536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen if (Addr->use_empty()) { 7183481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner RecursivelyDeleteTriviallyDeadInstructions(Addr); 719536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen // This address is now available for reassignment, so erase the table entry; 720536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen // we don't want to match some completely different instruction. 721536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen SunkAddrs[Addr] = 0; 722536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen } 723dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 724dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 725dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 7269bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// OptimizeInlineAsmInst - If there are any memory operands, use 72788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// OptimizeMemoryInst to sink their address computing into the block when 7289bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// possible / profitable. 7299bf12b5583104c810cfadcdce91edf9efad79973Evan Chengbool CodeGenPrepare::OptimizeInlineAsmInst(Instruction *I, CallSite CS, 7309bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng DenseMap<Value*,Value*> &SunkAddrs) { 7319bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng bool MadeChange = false; 7329bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng InlineAsm *IA = cast<InlineAsm>(CS.getCalledValue()); 7339bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 7349bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Do a prepass over the constraints, canonicalizing them, and building up the 7359bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // ConstraintOperands list. 7369bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng std::vector<InlineAsm::ConstraintInfo> 7379bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng ConstraintInfos = IA->ParseConstraints(); 7389bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 7399bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng /// ConstraintOperands - Information about all of the constraints. 7409bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng std::vector<TargetLowering::AsmOperandInfo> ConstraintOperands; 7419bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng unsigned ArgNo = 0; // ArgNo - The argument of the CallInst. 7429bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng for (unsigned i = 0, e = ConstraintInfos.size(); i != e; ++i) { 7439bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng ConstraintOperands. 7449bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng push_back(TargetLowering::AsmOperandInfo(ConstraintInfos[i])); 7459bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng TargetLowering::AsmOperandInfo &OpInfo = ConstraintOperands.back(); 7469bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 7479bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Compute the value type for each operand. 7489bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng switch (OpInfo.Type) { 7499bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng case InlineAsm::isOutput: 7509bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng if (OpInfo.isIndirect) 7519bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng OpInfo.CallOperandVal = CS.getArgument(ArgNo++); 7529bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng break; 7539bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng case InlineAsm::isInput: 7549bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng OpInfo.CallOperandVal = CS.getArgument(ArgNo++); 7559bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng break; 7569bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng case InlineAsm::isClobber: 7579bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Nothing to do. 7589bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng break; 7599bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng } 7609bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 7619bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Compute the constraint code and ConstraintType to use. 762a7e6146688f4b1f0f0651af4df4994e78d438377Evan Cheng TLI->ComputeConstraintToUse(OpInfo, SDValue(), 763a7e6146688f4b1f0f0651af4df4994e78d438377Evan Cheng OpInfo.ConstraintType == TargetLowering::C_Memory); 7649bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 7659ec8095485c994522c9a50e16fc029de94c20476Eli Friedman if (OpInfo.ConstraintType == TargetLowering::C_Memory && 7669ec8095485c994522c9a50e16fc029de94c20476Eli Friedman OpInfo.isIndirect) { 7679bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng Value *OpVal = OpInfo.CallOperandVal; 76888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner MadeChange |= OptimizeMemoryInst(I, OpVal, OpVal->getType(), SunkAddrs); 7699bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng } 7709bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng } 7719bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 7729bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng return MadeChange; 7739bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng} 7749bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 775b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// MoveExtToFormExtLoad - Move a zext or sext fed by a load into the same 776b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// basic block as the load, unless conditions are unfavorable. This allows 777b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// SelectionDAG to fold the extend into the load. 778b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// 779b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohmanbool CodeGenPrepare::MoveExtToFormExtLoad(Instruction *I) { 780b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Look for a load being extended. 781b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LoadInst *LI = dyn_cast<LoadInst>(I->getOperand(0)); 782b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (!LI) return false; 783b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 784b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // If they're already in the same block, there's nothing to do. 785b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (LI->getParent() == I->getParent()) 786b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 787b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 788b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // If the load has other users and the truncate is not free, this probably 789b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // isn't worthwhile. 790b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (!LI->hasOneUse() && 791b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman TLI && !TLI->isTruncateFree(I->getType(), LI->getType())) 792b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 793b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 794b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Check whether the target supports casts folded into loads. 795b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman unsigned LType; 796b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (isa<ZExtInst>(I)) 797b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LType = ISD::ZEXTLOAD; 798b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman else { 799b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman assert(isa<SExtInst>(I) && "Unexpected ext type!"); 800b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LType = ISD::SEXTLOAD; 801b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman } 802b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (TLI && !TLI->isLoadExtLegal(LType, TLI->getValueType(LI->getType()))) 803b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 804b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 805b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Move the extend into the same block as the load, so that SelectionDAG 806b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // can fold it. 807b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman I->removeFromParent(); 808b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman I->insertAfter(LI); 809b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return true; 810b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman} 811b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 812bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Chengbool CodeGenPrepare::OptimizeExtUses(Instruction *I) { 813bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *DefBB = I->getParent(); 814bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 815bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // If both result of the {s|z}xt and its source are live out, rewrite all 816bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // other uses of the source with result of extension. 817bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Value *Src = I->getOperand(0); 818bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (Src->hasOneUse()) 819bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 820bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 821696e5c047bd06bf6b7b5471b3f4dec319b43628bEvan Cheng // Only do this xform if truncating is free. 82253bdbd756581a9a1d6d381059f103c5f3c687bb6Gabor Greif if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType())) 823f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng return false; 824f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng 825772de516b6851e679d3da9e5171712b9c3122019Evan Cheng // Only safe to perform the optimization if the source is also defined in 826765dff258545f019502023045b471443ff9ef6c4Evan Cheng // this block. 827765dff258545f019502023045b471443ff9ef6c4Evan Cheng if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent()) 828772de516b6851e679d3da9e5171712b9c3122019Evan Cheng return false; 829772de516b6851e679d3da9e5171712b9c3122019Evan Cheng 830bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool DefIsLiveOut = false; 831692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 832bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 833bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 834bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 835bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 836bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 837bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 838bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DefIsLiveOut = true; 839bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng break; 840bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 841bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!DefIsLiveOut) 842bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 843bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 844765dff258545f019502023045b471443ff9ef6c4Evan Cheng // Make sure non of the uses are PHI nodes. 845692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 846765dff258545f019502023045b471443ff9ef6c4Evan Cheng UI != E; ++UI) { 847765dff258545f019502023045b471443ff9ef6c4Evan Cheng Instruction *User = cast<Instruction>(*UI); 848f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng BasicBlock *UserBB = User->getParent(); 849f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (UserBB == DefBB) continue; 850f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // Be conservative. We don't want this xform to end up introducing 851f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // reloads just before load / store instructions. 852f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User)) 853765dff258545f019502023045b471443ff9ef6c4Evan Cheng return false; 854765dff258545f019502023045b471443ff9ef6c4Evan Cheng } 855765dff258545f019502023045b471443ff9ef6c4Evan Cheng 856bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // InsertedTruncs - Only insert one trunc in each block once. 857bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DenseMap<BasicBlock*, Instruction*> InsertedTruncs; 858bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 859bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool MadeChange = false; 860692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 861bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 862bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Use &TheUse = UI.getUse(); 863bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 864bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 865bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 866bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 867bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 868bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 869bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Both src and def are live in this block. Rewrite the use. 870bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *&InsertedTrunc = InsertedTruncs[UserBB]; 871bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 872bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!InsertedTrunc) { 87302dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 874692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 875bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt); 876bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 877bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 878bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Replace a use of the {s|z}ext source with a use of the result. 879bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng TheUse = InsertedTrunc; 880bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 881bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange = true; 882bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 883bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 884bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return MadeChange; 885bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng} 886bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 887dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// In this pass we look for GEP and cast instructions that are used 888dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// across basic blocks and rewrite them to improve basic-block-at-a-time 889dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// selection. 890dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { 891dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 892692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 893ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng // Split all critical edges where the dest block has a PHI. 894dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TerminatorInst *BBTI = BB.getTerminator(); 895a4b04210d4a838e5a48b0c128bdfe42c3055633fChris Lattner if (BBTI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(BBTI)) { 896ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng for (unsigned i = 0, e = BBTI->getNumSuccessors(); i != e; ++i) { 897ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng BasicBlock *SuccBB = BBTI->getSuccessor(i); 898ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng if (isa<PHINode>(SuccBB->begin()) && isCriticalEdge(BBTI, i, true)) 899ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng SplitEdgeNicely(BBTI, i, BackEdges, this); 900ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng } 901dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 902692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 903dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Keep track of non-local addresses that have been sunk into this block. 904dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This allows us to avoid inserting duplicate code for blocks with multiple 905dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // load/stores of the same address. 906dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DenseMap<Value*, Value*> SunkAddrs; 907692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 908dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (BasicBlock::iterator BBI = BB.begin(), E = BB.end(); BBI != E; ) { 909dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *I = BBI++; 910692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 911dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (CastInst *CI = dyn_cast<CastInst>(I)) { 912dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If the source of the cast is a constant, then this should have 913dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // already been constant folded. The only reason NOT to constant fold 914dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // it is if something (e.g. LSR) was careful to place the constant 915dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // evaluation in a block other than then one that uses it (e.g. to hoist 916dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // the address of globals out of a loop). If this is the case, we don't 917dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // want to forward-subst the cast. 918dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (isa<Constant>(CI->getOperand(0))) 919dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner continue; 920692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 921bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool Change = false; 922bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (TLI) { 923bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Change = OptimizeNoopCopyExpression(CI, *TLI); 924bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange |= Change; 925bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 926bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 927b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (!Change && (isa<ZExtInst>(I) || isa<SExtInst>(I))) { 928b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman MadeChange |= MoveExtToFormExtLoad(I); 929bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange |= OptimizeExtUses(I); 930b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman } 931ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } else if (CmpInst *CI = dyn_cast<CmpInst>(I)) { 932ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen MadeChange |= OptimizeCmpExpression(CI); 933dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 934dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI) 93588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner MadeChange |= OptimizeMemoryInst(I, I->getOperand(0), LI->getType(), 93688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner SunkAddrs); 937dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 938dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI) 93988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner MadeChange |= OptimizeMemoryInst(I, SI->getOperand(1), 94088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner SI->getOperand(0)->getType(), 94188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner SunkAddrs); 942dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 943f25646bfb375b614cddcc8b6fda2b524feae1efaChris Lattner if (GEPI->hasAllZeroIndices()) { 944dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner /// The GEP operand must be a pointer, so must its result -> BitCast 945692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 946dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->getName(), GEPI); 947dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->replaceAllUsesWith(NC); 948dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->eraseFromParent(); 949dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner MadeChange = true; 950dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner BBI = NC; 951dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 952dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (CallInst *CI = dyn_cast<CallInst>(I)) { 953dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If we found an inline asm expession, and if the target knows how to 954dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // lower it to normal LLVM code, do so now. 9558850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner if (TLI && isa<InlineAsm>(CI->getCalledValue())) { 9568850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner if (TLI->ExpandInlineAsm(CI)) { 9578850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner BBI = BB.begin(); 9588850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner // Avoid processing instructions out of order, which could cause 9598850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner // reuse before a value is defined. 9608850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner SunkAddrs.clear(); 9618850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner } else 9628850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner // Sink address computing for memory operands into the block. 9638850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner MadeChange |= OptimizeInlineAsmInst(I, &(*CI), SunkAddrs); 964040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher } else { 965040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // Other CallInst optimizations that don't need to muck with the 966040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // enclosing iterator here. 967040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher MadeChange |= OptimizeCallInst(CI); 9688850b36d0fdd2ddde3cc409a8496ace544e42185Chris Lattner } 969dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 970dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 971692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 972dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 973dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 974