CodeGenPrepare.cpp revision 7c8d351d997655eb457bac5f810c219a9089594c
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" 2580f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich#include "llvm/Analysis/Dominators.h" 26d5f8684b16057df73771b23e293b400cb327e079Owen Anderson#include "llvm/Analysis/InstructionSimplify.h" 27ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter#include "llvm/Analysis/ProfileInfo.h" 28dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetData.h" 29dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetLowering.h" 30a1fd5b386dd8eb4c86bfd2b9659c219a1c4f56dbEvan Cheng#include "llvm/Transforms/Utils/AddrModeMatcher.h" 31dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 32dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Transforms/Utils/Local.h" 33040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher#include "llvm/Transforms/Utils/BuildLibCalls.h" 34dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/ADT/DenseMap.h" 35dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/ADT/SmallSet.h" 367eb589d3f9294dbfe4d5205045bd8119a9666532Jakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 3703ce042d70c423a41edca0714112a0e06b16493bDan Gohman#include "llvm/Assembly/Writer.h" 389bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng#include "llvm/Support/CallSite.h" 39e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng#include "llvm/Support/CommandLine.h" 40bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng#include "llvm/Support/Debug.h" 41dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 42088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner#include "llvm/Support/PatternMatch.h" 436c1980b3357207c4d756255bc5e32323eac278dcDan Gohman#include "llvm/Support/raw_ostream.h" 44040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher#include "llvm/Support/IRBuilder.h" 4594e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner#include "llvm/Support/ValueHandle.h" 46dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerusing namespace llvm; 47088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattnerusing namespace llvm::PatternMatch; 48dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 4931ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumBlocksElim, "Number of blocks eliminated"); 50073057f0d0a1e21ab020fa71ff4bd11543faa6d0Cameron ZwarichSTATISTIC(NumPHIsElim, "Number of trivial PHIs eliminated"); 51073057f0d0a1e21ab020fa71ff4bd11543faa6d0Cameron ZwarichSTATISTIC(NumGEPsElim, "Number of GEPs converted to casts"); 5231ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumCmpUses, "Number of uses of Cmp expressions replaced with uses of " 5331ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich "sunken Cmps"); 5431ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumCastUses, "Number of uses of Cast expressions replaced with uses " 5531ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich "of sunken Casts"); 5631ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumMemoryInsts, "Number of memory instructions whose address " 5731ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich "computations were sunk"); 5831ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumExtsMoved, "Number of [s|z]ext instructions combined with loads"); 5931ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumExtUses, "Number of uses of [s|z]ext instructions optimized"); 607eb589d3f9294dbfe4d5205045bd8119a9666532Jakob Stoklund Olesen 61692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christophernamespace { 623e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class CodeGenPrepare : public FunctionPass { 63dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// TLI - Keep a pointer of a TargetLowering to consult for determining 64dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// transformation profitability. 65dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner const TargetLowering *TLI; 6680f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DominatorTree *DT; 6704149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng ProfileInfo *PFI; 687579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner 697579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner /// CurInstIterator - As we scan instructions optimizing them, this is the 707579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner /// next instruction to optimize. Xforms that can invalidate this should 717579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner /// update it. 727579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner BasicBlock::iterator CurInstIterator; 73ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 748c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich // Keeps track of non-local addresses that have been sunk into a block. This 758c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich // allows us to avoid inserting duplicate code for blocks with multiple 768c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich // load/stores of the same address. 778c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich DenseMap<Value*, Value*> SunkAddrs; 788c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich 79dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner public: 80ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 81c2bbfc18e9adbbdcf5b3375d8d25e2452f7df7f1Dan Gohman explicit CodeGenPrepare(const TargetLowering *tli = 0) 82081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson : FunctionPass(ID), TLI(tli) { 83081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeCodeGenPreparePass(*PassRegistry::getPassRegistry()); 84081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 85dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool runOnFunction(Function &F); 86692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 87ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter virtual void getAnalysisUsage(AnalysisUsage &AU) const { 8880f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich AU.addPreserved<DominatorTree>(); 89ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter AU.addPreserved<ProfileInfo>(); 90ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 91ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter 92dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner private: 93d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool EliminateMostlyEmptyBlocks(Function &F); 94d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; 95d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner void EliminateMostlyEmptyBlock(BasicBlock *BB); 96dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool OptimizeBlock(BasicBlock &BB); 97c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich bool OptimizeInst(Instruction *I); 981a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner bool OptimizeMemoryInst(Instruction *I, Value *Addr, const Type *AccessTy); 997579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner bool OptimizeInlineAsmInst(CallInst *CS); 100040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher bool OptimizeCallInst(CallInst *CI); 101b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman bool MoveExtToFormExtLoad(Instruction *I); 102bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool OptimizeExtUses(Instruction *I); 103dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner }; 104dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 105794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 1061997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar CodeGenPrepare::ID = 0; 107d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(CodeGenPrepare, "codegenprepare", 108ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Optimize for code generation", false, false) 109dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 110dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris LattnerFunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { 111dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return new CodeGenPrepare(TLI); 112dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 113dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 114dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::runOnFunction(Function &F) { 115dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool EverMadeChange = false; 116692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 11780f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DT = getAnalysisIfAvailable<DominatorTree>(); 11804149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI = getAnalysisIfAvailable<ProfileInfo>(); 119d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // First pass, eliminate blocks that contain only PHI nodes and an 120d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // unconditional branch. 121d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EverMadeChange |= EliminateMostlyEmptyBlocks(F); 122692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 123d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = true; 124dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner while (MadeChange) { 125dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = false; 126dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 127dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange |= OptimizeBlock(*BB); 128dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner EverMadeChange |= MadeChange; 129dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 1308c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich 1318c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich SunkAddrs.clear(); 1328c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich 133dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return EverMadeChange; 134dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 135dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 1362d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes, 1372d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// debug info directives, and an unconditional branch. Passes before isel 1382d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// (e.g. LSR/loopsimplify) often split edges in ways that are non-optimal for 1392d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// isel. Start by eliminating these blocks so we can split them the way we 1402d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// want them. 141d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) { 142d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = false; 143d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Note that this intentionally skips the entry block. 144d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) { 145d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *BB = I++; 146d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 147d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If this block doesn't end with an uncond branch, ignore it. 148d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 149d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!BI || !BI->isUnconditional()) 150d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 151692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1522d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen // If the instruction before the branch (skipping debug info) isn't a phi 1532d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen // node, then other stuff is happening here. 154d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::iterator BBI = BI; 155d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBI != BB->begin()) { 156d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner --BBI; 1572d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen while (isa<DbgInfoIntrinsic>(BBI)) { 1582d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen if (BBI == BB->begin()) 1592d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen break; 1602d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen --BBI; 1612d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen } 1622d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI)) 1632d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen continue; 164d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 165692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 166d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Do not break infinite loops. 167d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 168d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (DestBB == BB) 169d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 170692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 171d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!CanMergeBlocks(BB, DestBB)) 172d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 173692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 174d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EliminateMostlyEmptyBlock(BB); 175d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner MadeChange = true; 176d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 177d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return MadeChange; 178d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 179d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 180d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a 181d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// single uncond branch between them, and BB contains no other non-phi 182d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// instructions. 183d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, 184d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const BasicBlock *DestBB) const { 185d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // We only want to eliminate blocks whose phi nodes are used by phi nodes in 186d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // the successor. If there are more complex condition (e.g. preheaders), 187d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // don't mess around with them. 188d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::const_iterator BBI = BB->begin(); 189d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 19060ad781c61815ca5b8dc2a45a102e1c8af65992fGabor Greif for (Value::const_use_iterator UI = PN->use_begin(), E = PN->use_end(); 191d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner UI != E; ++UI) { 192d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Instruction *User = cast<Instruction>(*UI); 193d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (User->getParent() != DestBB || !isa<PHINode>(User)) 194d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return false; 195692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If User is inside DestBB block and it is a PHINode then check 196692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // incoming value. If incoming value is not from BB then this is 19775abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel // a complex condition (e.g. preheaders) we want to avoid here. 19875abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (User->getParent() == DestBB) { 19975abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (const PHINode *UPN = dyn_cast<PHINode>(User)) 20075abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { 20175abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); 20275abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (Insn && Insn->getParent() == BB && 20375abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Insn->getParent() != UPN->getIncomingBlock(I)) 20475abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel return false; 20575abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 20675abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 207d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 208d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 209692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 210d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If BB and DestBB contain any common predecessors, then the phi nodes in BB 211d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // and DestBB may have conflicting incoming values for the block. If so, we 212d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // can't merge the block. 213d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); 214d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!DestBBPN) return true; // no conflict. 215692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 216d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Collect the preds of BB. 217f67f73a519eac94b6c1f98dbce7d251a3a4aea07Chris Lattner SmallPtrSet<const BasicBlock*, 16> BBPreds; 218d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 219d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // It is faster to get preds from a PHI than with pred_iterator. 220d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 221d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(BBPN->getIncomingBlock(i)); 222d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 223d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(pred_begin(BB), pred_end(BB)); 224d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 225692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 226d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Walk the preds of DestBB. 227d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { 228d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *Pred = DestBBPN->getIncomingBlock(i); 229d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBPreds.count(Pred)) { // Common predecessor? 230d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBI = DestBB->begin(); 231d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 232d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V1 = PN->getIncomingValueForBlock(Pred); 233d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V2 = PN->getIncomingValueForBlock(BB); 234692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 235d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If V2 is a phi node in BB, look up what the mapped value will be. 236d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) 237d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V2PN->getParent() == BB) 238d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner V2 = V2PN->getIncomingValueForBlock(Pred); 239692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 240d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If there is a conflict, bail out. 241d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V1 != V2) return false; 242d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 243d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 244d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 245d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 246d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return true; 247d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 248d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 249d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 250d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and 251d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// an unconditional branch in it. 252d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnervoid CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { 253d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 254d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 255692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 25668d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB); 257692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 258d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If the destination block has a single pred, then this is a trivial edge, 259d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // just collapse it. 2609918fb5631974f2201a640384b7ebe672c749e43Chris Lattner if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) { 261f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (SinglePred != DestBB) { 262f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // Remember if SinglePred was the entry block of the function. If so, we 263f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // will need to move BB back to the entry position. 264f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 265ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter MergeBasicBlockIntoOnlyPred(DestBB, this); 266f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 267f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (isEntry && BB != &BB->getParent()->getEntryBlock()) 268f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner BB->moveBefore(&BB->getParent()->getEntryBlock()); 269f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 27068d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 271f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner return; 272f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner } 273d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 274692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 275d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB 276d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // to handle the new incoming edges it is about to have. 277d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *PN; 278d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (BasicBlock::iterator BBI = DestBB->begin(); 279d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 280d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Remove the incoming value for BB, and remember it. 281d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner Value *InVal = PN->removeIncomingValue(BB, false); 282692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 283d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Two options: either the InVal is a phi node defined in BB or it is some 284d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // value that dominates BB. 285d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *InValPhi = dyn_cast<PHINode>(InVal); 286d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (InValPhi && InValPhi->getParent() == BB) { 287d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Add all of the input values of the input PHI as inputs of this phi. 288d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) 289d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InValPhi->getIncomingValue(i), 290d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner InValPhi->getIncomingBlock(i)); 291d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 292d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, add one instance of the dominating value for each edge that 293d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // we will be adding. 294d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 295d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 296d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); 297d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 298d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 299d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, *PI); 300d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 301d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 302d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 303692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 304d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // The PHIs are now updated, change everything that refers to BB to use 305d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // DestBB and remove BB. 306d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->replaceAllUsesWith(DestBB); 30780f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich if (DT) { 30880f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich BasicBlock *BBIDom = DT->getNode(BB)->getIDom()->getBlock(); 30980f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich BasicBlock *DestBBIDom = DT->getNode(DestBB)->getIDom()->getBlock(); 31080f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich BasicBlock *NewIDom = DT->findNearestCommonDominator(BBIDom, DestBBIDom); 31180f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DT->changeImmediateDominator(DestBB, NewIDom); 31280f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DT->eraseNode(BB); 31380f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich } 31404149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng if (PFI) { 31504149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI->replaceAllUses(BB, DestBB); 31604149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI->removeEdge(ProfileInfo::getEdge(BB, DestBB)); 317ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 318d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->eraseFromParent(); 31931ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumBlocksElim; 320692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 32168d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 322d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 323d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 324dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// OptimizeNoopCopyExpression - If the specified cast instruction is a noop 325a119de86a064414622562cfe32953de7f9b0ee40Dan Gohman/// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC), 326a119de86a064414622562cfe32953de7f9b0ee40Dan Gohman/// sink it into user blocks to reduce the number of virtual 327ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// registers that must be created and coalesced. 328dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// 329dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// Return true if any changes are made. 33085fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner/// 331dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){ 332692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If this is a noop copy, 333e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 334e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT DstVT = TLI.getValueType(CI->getType()); 335692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 336dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This is an fp<->int conversion? 33783ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands if (SrcVT.isInteger() != DstVT.isInteger()) 338dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 3398e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands 340dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is an extension, it will be a zero or sign extension, which 341dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // isn't a noop. 3428e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands if (SrcVT.bitsLT(DstVT)) return false; 343692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 344dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If these values will be promoted, find out what they will be promoted 345dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // to. This helps us consider truncates on PPC as noop copies when they 346dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // are. 347aafe626c7fa9f99150cccd27d0151a2cf7c8c00bChris Lattner if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) 34823b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT); 349aafe626c7fa9f99150cccd27d0151a2cf7c8c00bChris Lattner if (TLI.getTypeAction(DstVT) == TargetLowering::Promote) 35023b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT); 351692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 352dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If, after promotion, these are the same types, this is a noop copy. 353dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SrcVT != DstVT) 354dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 355692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 356dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *DefBB = CI->getParent(); 357692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 358dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// InsertedCasts - Only insert a cast in each block once. 359ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CastInst*> InsertedCasts; 360692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 361dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 362692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 363dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner UI != E; ) { 364dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Use &TheUse = UI.getUse(); 365dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *User = cast<Instruction>(*UI); 366692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 367dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Figure out which BB this cast is used in. For PHI's this is the 368dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // appropriate predecessor block. 369dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *UserBB = User->getParent(); 370dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) { 371a36791da41cf4f635e50077b290676b873836bdaGabor Greif UserBB = PN->getIncomingBlock(UI); 372dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 373692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 374dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Preincrement use iterator so we don't invalidate it. 375dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner ++UI; 376692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 377dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If this user is in the same block as the cast, don't change the cast. 378dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (UserBB == DefBB) continue; 379692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 380dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we have already inserted a cast into this block, use it. 381dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CastInst *&InsertedCast = InsertedCasts[UserBB]; 382dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 383dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (!InsertedCast) { 38402dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 385692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 386692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCast = 387692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 388dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner InsertPt); 389dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = true; 390dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 391692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 392ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cast with a use of the new cast. 393dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TheUse = InsertedCast; 39431ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumCastUses; 395dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 396692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 397dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we removed all uses, nuke the cast. 398e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands if (CI->use_empty()) { 399dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CI->eraseFromParent(); 400e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands MadeChange = true; 401e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands } 402692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 403dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 404dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 405dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 406692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher/// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce 407ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// the number of virtual registers that must be created and coalesced. This is 408684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// a clear win except on targets with multiple condition code registers 409684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// (PowerPC), where it might lose; some adjustment may be wanted there. 410ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// 411ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// Return true if any changes are made. 41285fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattnerstatic bool OptimizeCmpExpression(CmpInst *CI) { 413ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *DefBB = CI->getParent(); 414692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 415ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen /// InsertedCmp - Only insert a cmp in each block once. 416ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CmpInst*> InsertedCmps; 417692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 418ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen bool MadeChange = false; 419692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 420ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen UI != E; ) { 421ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Use &TheUse = UI.getUse(); 422ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Instruction *User = cast<Instruction>(*UI); 423692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 424ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Preincrement use iterator so we don't invalidate it. 425ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen ++UI; 426692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 427ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Don't bother for PHI nodes. 428ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (isa<PHINode>(User)) 429ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen continue; 430ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 431ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Figure out which BB this cmp is used in. 432ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *UserBB = User->getParent(); 433692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 434ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If this user is in the same block as the cmp, don't change the cmp. 435ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (UserBB == DefBB) continue; 436692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 437ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we have already inserted a cmp into this block, use it. 438ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CmpInst *&InsertedCmp = InsertedCmps[UserBB]; 439ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 440ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (!InsertedCmp) { 44102dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 442692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 443692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCmp = 4441c8a23c440b1665ba422778cdc74a0c59ecaf39eDan Gohman CmpInst::Create(CI->getOpcode(), 445333c40096561218bc3597cf153c0a3895274414cOwen Anderson CI->getPredicate(), CI->getOperand(0), 446ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->getOperand(1), "", InsertPt); 447ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen MadeChange = true; 448ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 449692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 450ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cmp with a use of the new cmp. 451ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen TheUse = InsertedCmp; 45231ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumCmpUses; 453ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 454692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 455ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we removed all uses, nuke the cmp. 456ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (CI->use_empty()) 457ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->eraseFromParent(); 458692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 459ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen return MadeChange; 460ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen} 461ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 4620b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramernamespace { 4630b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramerclass CodeGenPrepareFortifiedLibCalls : public SimplifyFortifiedLibCalls { 4640b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramerprotected: 4650b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer void replaceCall(Value *With) { 4660b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CI->replaceAllUsesWith(With); 4670b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CI->eraseFromParent(); 4680b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer } 4690b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer bool isFoldable(unsigned SizeCIOp, unsigned, bool) const { 470a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif if (ConstantInt *SizeCI = 471a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) 472a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif return SizeCI->isAllOnesValue(); 4730b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer return false; 4740b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer } 4750b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer}; 4760b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer} // end anonymous namespace 4770b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer 478040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopherbool CodeGenPrepare::OptimizeCallInst(CallInst *CI) { 4797579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner BasicBlock *BB = CI->getParent(); 4807579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner 4817579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Lower inline assembly if we can. 4827579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // If we found an inline asm expession, and if the target knows how to 4837579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // lower it to normal LLVM code, do so now. 4847579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner if (TLI && isa<InlineAsm>(CI->getCalledValue())) { 4857579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner if (TLI->ExpandInlineAsm(CI)) { 4867579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Avoid invalidating the iterator. 4877579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner CurInstIterator = BB->begin(); 4887579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Avoid processing instructions out of order, which could cause 4897579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // reuse before a value is defined. 4907579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner SunkAddrs.clear(); 4917579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner return true; 4927579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner } 4937579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Sink address computing for memory operands into the block. 4947579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner if (OptimizeInlineAsmInst(CI)) 4957579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner return true; 4967579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner } 4977579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner 498040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // Lower all uses of llvm.objectsize.* 499040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI); 500040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (II && II->getIntrinsicID() == Intrinsic::objectsize) { 501de9f5452d3ae894bb7fdd455cec5af50e2560aa5Gabor Greif bool Min = (cast<ConstantInt>(II->getArgOperand(1))->getZExtValue() == 1); 502040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher const Type *ReturnTy = CI->getType(); 503040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL); 50494e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner 50594e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner // Substituting this can cause recursive simplifications, which can 50694e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner // invalidate our iterator. Use a WeakVH to hold onto it in case this 50794e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner // happens. 50894e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner WeakVH IterHandle(CurInstIterator); 50994e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner 51094e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner ReplaceAndSimplifyAllUses(CI, RetVal, TLI ? TLI->getTargetData() : 0, DT); 51194e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner 51294e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner // If the iterator instruction was recursively deleted, start over at the 51394e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner // start of the block. 514435b4d2eba723e9513453f20885244ad1d16e0d4Chris Lattner if (IterHandle != CurInstIterator) { 51594e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner CurInstIterator = BB->begin(); 516435b4d2eba723e9513453f20885244ad1d16e0d4Chris Lattner SunkAddrs.clear(); 517435b4d2eba723e9513453f20885244ad1d16e0d4Chris Lattner } 518040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher return true; 519040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher } 520040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 521040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // From here on out we're working with named functions. 522040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (CI->getCalledFunction() == 0) return false; 523040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 524040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // We'll need TargetData from here on out. 525040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher const TargetData *TD = TLI ? TLI->getTargetData() : 0; 526040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (!TD) return false; 527040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 5280b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer // Lower all default uses of _chk calls. This is very similar 5290b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer // to what InstCombineCalls does, but here we are only lowering calls 530040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // that have the default "don't know" as the objectsize. Anything else 531040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // should be left alone. 5320b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CodeGenPrepareFortifiedLibCalls Simplifier; 5330b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer return Simplifier.fold(CI, TD); 534040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher} 53594e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner 53688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 53788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner// Memory Optimization 53888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 53988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 540dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// IsNonLocalValue - Return true if the specified values are defined in a 541dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// different basic block than BB. 542dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool IsNonLocalValue(Value *V, BasicBlock *BB) { 543dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 544dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return I->getParent() != BB; 545dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 546dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 547dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 5484a8ee23a8181f668dc294b417f67e1675ad391abBob Wilson/// OptimizeMemoryInst - Load and Store Instructions often have 549dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// addressing modes that can do significant amounts of computation. As such, 550dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// instruction selection will try to get the load or store to do as much 551dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// computation as possible for the program. The problem is that isel can only 552dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// see within a single block. As such, we sink as much legal addressing mode 553dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// stuff into the block as possible. 55488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// 55588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// This method is used to optimize both load/store and inline asms with memory 55688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// operands. 557896617b776e7b015346160645b19be776cbe3805Chris Lattnerbool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr, 5581a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner const Type *AccessTy) { 55935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Value *Repl = Addr; 56035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 561d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson // Try to collapse single-value PHI nodes. This is necessary to undo 562d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson // unprofitable PRE transformations. 5637cb4fa20b5534decf527a6bfcc74bd79ea11cbb1Cameron Zwarich SmallVector<Value*, 8> worklist; 5647cb4fa20b5534decf527a6bfcc74bd79ea11cbb1Cameron Zwarich SmallPtrSet<Value*, 16> Visited; 56535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson worklist.push_back(Addr); 56635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 56735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // Use a worklist to iteratively look through PHI nodes, and ensure that 56835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // the addressing mode obtained from the non-PHI roots of the graph 56935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // are equivalent. 57035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Value *Consensus = 0; 5714c078f0d6df6136cbbcf581c254869051d455fdcCameron Zwarich unsigned NumUsesConsensus = 0; 5727c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich bool IsNumUsesConsensusValid = false; 57335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson SmallVector<Instruction*, 16> AddrModeInsts; 57435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson ExtAddrMode AddrMode; 57535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson while (!worklist.empty()) { 57635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Value *V = worklist.back(); 57735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson worklist.pop_back(); 57835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 57935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // Break use-def graph loops. 58035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (Visited.count(V)) { 58135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Consensus = 0; 58235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson break; 58335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson } 58435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 58535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Visited.insert(V); 58635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 58735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // For a PHI node, push all of its incoming values. 58835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (PHINode *P = dyn_cast<PHINode>(V)) { 58935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) 59035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson worklist.push_back(P->getIncomingValue(i)); 59135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson continue; 59235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson } 59335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 59435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // For non-PHIs, determine the addressing mode being computed. 59535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson SmallVector<Instruction*, 16> NewAddrModeInsts; 59635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson ExtAddrMode NewAddrMode = 59735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson AddressingModeMatcher::Match(V, AccessTy,MemoryInst, 59835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson NewAddrModeInsts, *TLI); 5997c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich 6007c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // This check is broken into two cases with very similar code to avoid using 6017c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // getNumUses() as much as possible. Some values have a lot of uses, so 6027c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // calling getNumUses() unconditionally caused a significant compile-time 6037c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // regression. 6047c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich if (!Consensus) { 6057c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich Consensus = V; 6067c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich AddrMode = NewAddrMode; 6077c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich AddrModeInsts = NewAddrModeInsts; 6087c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich continue; 6097c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich } else if (NewAddrMode == AddrMode) { 6107c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich if (!IsNumUsesConsensusValid) { 6117c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich NumUsesConsensus = Consensus->getNumUses(); 6127c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich IsNumUsesConsensusValid = true; 6137c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich } 6147c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich 6157c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // Ensure that the obtained addressing mode is equivalent to that obtained 6167c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // for all other roots of the PHI traversal. Also, when choosing one 6177c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // such root as representative, select the one with the most uses in order 6187c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // to keep the cost modeling heuristics in AddressingModeMatcher 6197c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // applicable. 6204c078f0d6df6136cbbcf581c254869051d455fdcCameron Zwarich unsigned NumUses = V->getNumUses(); 6214c078f0d6df6136cbbcf581c254869051d455fdcCameron Zwarich if (NumUses > NumUsesConsensus) { 62235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Consensus = V; 6234c078f0d6df6136cbbcf581c254869051d455fdcCameron Zwarich NumUsesConsensus = NumUses; 62435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson AddrModeInsts = NewAddrModeInsts; 625d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson } 62635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson continue; 627d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson } 628d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson 62935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Consensus = 0; 63035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson break; 631d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson } 632d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson 63335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // If the addressing mode couldn't be determined, or if multiple different 63435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // ones were determined, bail out now. 63535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (!Consensus) return false; 63635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 637dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if any of the instructions supersumed by this addr mode are 638dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // non-local to I's BB. 639dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool AnyNonLocal = false; 640dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { 641896617b776e7b015346160645b19be776cbe3805Chris Lattner if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) { 642dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AnyNonLocal = true; 643dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 644dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 645dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 646692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 647dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If all the instructions matched are already in this BB, don't do anything. 648dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!AnyNonLocal) { 64968d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: Found local addrmode: " << AddrMode << "\n"); 650dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 651dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 652692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 653dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Insert this computation right after this user. Since our caller is 654dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // scanning from the top of the BB to the bottom, reuse of the expr are 655dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // guaranteed to happen later. 656896617b776e7b015346160645b19be776cbe3805Chris Lattner BasicBlock::iterator InsertPt = MemoryInst; 657692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 658dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Now that we determined the addressing expression we want to use and know 659dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // that we have to sink it into this block. Check to see if we have already 660dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done this for some other load/store instr in this block. If so, reuse the 661dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // computation. 662dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *&SunkAddr = SunkAddrs[Addr]; 663dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr) { 66468d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for " 6656c1980b3357207c4d756255bc5e32323eac278dcDan Gohman << *MemoryInst); 666dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr->getType() != Addr->getType()) 667dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new BitCastInst(SunkAddr, Addr->getType(), "tmp", InsertPt); 668dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 66968d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for " 6706c1980b3357207c4d756255bc5e32323eac278dcDan Gohman << *MemoryInst); 6711d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson const Type *IntPtrTy = 6721d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson TLI->getTargetData()->getIntPtrType(AccessTy->getContext()); 673692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 674dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *Result = 0; 675d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman 676d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // Start with the base register. Do this first so that subsequent address 677d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // matching finds it last, which will prevent it from trying to match it 678d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // as the scaled value in case it happens to be a mul. That would be 679d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // problematic if we've sunk a different mul for the scale, because then 680d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // we'd end up sinking both muls. 681d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman if (AddrMode.BaseReg) { 682d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman Value *V = AddrMode.BaseReg; 6831df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (V->getType()->isPointerTy()) 684d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 685d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman if (V->getType() != IntPtrTy) 686d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman V = CastInst::CreateIntegerCast(V, IntPtrTy, /*isSigned=*/true, 687d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman "sunkaddr", InsertPt); 688d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman Result = V; 689d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman } 690d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman 691d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // Add the scale value. 692dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale) { 693dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = AddrMode.ScaledReg; 694dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (V->getType() == IntPtrTy) { 695dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done. 6961df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands } else if (V->getType()->isPointerTy()) { 697dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 698dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 699dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cast<IntegerType>(V->getType())->getBitWidth()) { 700dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new TruncInst(V, IntPtrTy, "sunkaddr", InsertPt); 701dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 702dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new SExtInst(V, IntPtrTy, "sunkaddr", InsertPt); 703dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 704dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale != 1) 705eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson V = BinaryOperator::CreateMul(V, ConstantInt::get(IntPtrTy, 706d672ecb0178c6247a5eaa5b0fb0c3b23cd25bd7cOwen Anderson AddrMode.Scale), 707dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner "sunkaddr", InsertPt); 708dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 7097cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 710dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 711dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 712dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 713692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 714dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the BaseGV if present. 715dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseGV) { 716dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = new PtrToIntInst(AddrMode.BaseGV, IntPtrTy, "sunkaddr", 717dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner InsertPt); 718dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 7197cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 720dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 721dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 722dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 723692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 724dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the Base Offset if present. 725dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseOffs) { 726eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 727dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 7287cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 729dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 730dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 731dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 732dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 733dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result == 0) 734a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson SunkAddr = Constant::getNullValue(Addr->getType()); 735dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 736dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new IntToPtrInst(Result, Addr->getType(), "sunkaddr",InsertPt); 737dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 738692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 739d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson MemoryInst->replaceUsesOfWith(Repl, SunkAddr); 740692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 741d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson if (Repl->use_empty()) { 742d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson RecursivelyDeleteTriviallyDeadInstructions(Repl); 743536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen // This address is now available for reassignment, so erase the table entry; 744536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen // we don't want to match some completely different instruction. 745536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen SunkAddrs[Addr] = 0; 746536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen } 74731ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumMemoryInsts; 748dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 749dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 750dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 7519bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// OptimizeInlineAsmInst - If there are any memory operands, use 75288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// OptimizeMemoryInst to sink their address computing into the block when 7539bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// possible / profitable. 7547579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattnerbool CodeGenPrepare::OptimizeInlineAsmInst(CallInst *CS) { 7559bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng bool MadeChange = false; 7569bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 7577579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner TargetLowering::AsmOperandInfoVector 7587579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner TargetConstraints = TLI->ParseConstraints(CS); 759677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen unsigned ArgNo = 0; 760eac6e1d0c748afc3d1496be0753ffbe5f5a4279bJohn Thompson for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) { 761eac6e1d0c748afc3d1496be0753ffbe5f5a4279bJohn Thompson TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i]; 762eac6e1d0c748afc3d1496be0753ffbe5f5a4279bJohn Thompson 7639bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Compute the constraint code and ConstraintType to use. 7641784d160e4efa75782884d451d0788b9457e67dcDale Johannesen TLI->ComputeConstraintToUse(OpInfo, SDValue()); 7659bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 7669ec8095485c994522c9a50e16fc029de94c20476Eli Friedman if (OpInfo.ConstraintType == TargetLowering::C_Memory && 7679ec8095485c994522c9a50e16fc029de94c20476Eli Friedman OpInfo.isIndirect) { 7687579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner Value *OpVal = CS->getArgOperand(ArgNo++); 7691a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner MadeChange |= OptimizeMemoryInst(CS, OpVal, OpVal->getType()); 770677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen } else if (OpInfo.Type == InlineAsm::isInput) 771677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen ArgNo++; 7729bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng } 7739bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 7749bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng return MadeChange; 7759bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng} 7769bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 777b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// MoveExtToFormExtLoad - Move a zext or sext fed by a load into the same 778b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// basic block as the load, unless conditions are unfavorable. This allows 779b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// SelectionDAG to fold the extend into the load. 780b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// 781b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohmanbool CodeGenPrepare::MoveExtToFormExtLoad(Instruction *I) { 782b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Look for a load being extended. 783b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LoadInst *LI = dyn_cast<LoadInst>(I->getOperand(0)); 784b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (!LI) return false; 785b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 786b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // If they're already in the same block, there's nothing to do. 787b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (LI->getParent() == I->getParent()) 788b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 789b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 790b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // If the load has other users and the truncate is not free, this probably 791b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // isn't worthwhile. 792b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (!LI->hasOneUse() && 793ec57a1acec7803fff2faa54c6ea8fec2be01aeb9Bob Wilson TLI && (TLI->isTypeLegal(TLI->getValueType(LI->getType())) || 794ec57a1acec7803fff2faa54c6ea8fec2be01aeb9Bob Wilson !TLI->isTypeLegal(TLI->getValueType(I->getType()))) && 79571dc4d96ed39fadcdccf8c578d49a1afdae0c6baBob Wilson !TLI->isTruncateFree(I->getType(), LI->getType())) 796b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 797b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 798b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Check whether the target supports casts folded into loads. 799b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman unsigned LType; 800b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (isa<ZExtInst>(I)) 801b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LType = ISD::ZEXTLOAD; 802b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman else { 803b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman assert(isa<SExtInst>(I) && "Unexpected ext type!"); 804b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LType = ISD::SEXTLOAD; 805b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman } 806b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (TLI && !TLI->isLoadExtLegal(LType, TLI->getValueType(LI->getType()))) 807b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 808b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 809b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Move the extend into the same block as the load, so that SelectionDAG 810b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // can fold it. 811b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman I->removeFromParent(); 812b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman I->insertAfter(LI); 81331ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumExtsMoved; 814b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return true; 815b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman} 816b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 817bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Chengbool CodeGenPrepare::OptimizeExtUses(Instruction *I) { 818bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *DefBB = I->getParent(); 819bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 8209120f5c35b756e0b9d7747616e97df8f30edfcc8Bob Wilson // If the result of a {s|z}ext and its source are both live out, rewrite all 821bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // other uses of the source with result of extension. 822bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Value *Src = I->getOperand(0); 823bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (Src->hasOneUse()) 824bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 825bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 826696e5c047bd06bf6b7b5471b3f4dec319b43628bEvan Cheng // Only do this xform if truncating is free. 82753bdbd756581a9a1d6d381059f103c5f3c687bb6Gabor Greif if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType())) 828f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng return false; 829f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng 830772de516b6851e679d3da9e5171712b9c3122019Evan Cheng // Only safe to perform the optimization if the source is also defined in 831765dff258545f019502023045b471443ff9ef6c4Evan Cheng // this block. 832765dff258545f019502023045b471443ff9ef6c4Evan Cheng if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent()) 833772de516b6851e679d3da9e5171712b9c3122019Evan Cheng return false; 834772de516b6851e679d3da9e5171712b9c3122019Evan Cheng 835bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool DefIsLiveOut = false; 836692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 837bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 838bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 839bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 840bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 841bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 842bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 843bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DefIsLiveOut = true; 844bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng break; 845bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 846bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!DefIsLiveOut) 847bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 848bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 849765dff258545f019502023045b471443ff9ef6c4Evan Cheng // Make sure non of the uses are PHI nodes. 850692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 851765dff258545f019502023045b471443ff9ef6c4Evan Cheng UI != E; ++UI) { 852765dff258545f019502023045b471443ff9ef6c4Evan Cheng Instruction *User = cast<Instruction>(*UI); 853f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng BasicBlock *UserBB = User->getParent(); 854f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (UserBB == DefBB) continue; 855f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // Be conservative. We don't want this xform to end up introducing 856f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // reloads just before load / store instructions. 857f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User)) 858765dff258545f019502023045b471443ff9ef6c4Evan Cheng return false; 859765dff258545f019502023045b471443ff9ef6c4Evan Cheng } 860765dff258545f019502023045b471443ff9ef6c4Evan Cheng 861bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // InsertedTruncs - Only insert one trunc in each block once. 862bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DenseMap<BasicBlock*, Instruction*> InsertedTruncs; 863bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 864bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool MadeChange = false; 865692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 866bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 867bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Use &TheUse = UI.getUse(); 868bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 869bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 870bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 871bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 872bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 873bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 874bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Both src and def are live in this block. Rewrite the use. 875bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *&InsertedTrunc = InsertedTruncs[UserBB]; 876bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 877bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!InsertedTrunc) { 87802dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 879692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 880bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt); 881bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 882bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 883bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Replace a use of the {s|z}ext source with a use of the result. 884bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng TheUse = InsertedTrunc; 88531ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumExtUses; 886bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange = true; 887bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 888bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 889bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return MadeChange; 890bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng} 891bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 892c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarichbool CodeGenPrepare::OptimizeInst(Instruction *I) { 893c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (PHINode *P = dyn_cast<PHINode>(I)) { 894c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // It is possible for very late stage optimizations (such as SimplifyCFG) 895c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // to introduce PHI nodes too late to be cleaned up. If we detect such a 896c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // trivial PHI, go ahead and zap it here. 897c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (Value *V = SimplifyInstruction(P)) { 898c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich P->replaceAllUsesWith(V); 899c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich P->eraseFromParent(); 900c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich ++NumPHIsElim; 9011a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return true; 902c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } 9031a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 9041a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner } 9051a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 9061a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (CastInst *CI = dyn_cast<CastInst>(I)) { 907c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // If the source of the cast is a constant, then this should have 908c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // already been constant folded. The only reason NOT to constant fold 909c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // it is if something (e.g. LSR) was careful to place the constant 910c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // evaluation in a block other than then one that uses it (e.g. to hoist 911c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // the address of globals out of a loop). If this is the case, we don't 912c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // want to forward-subst the cast. 913c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (isa<Constant>(CI->getOperand(0))) 914c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich return false; 915c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 9161a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (TLI && OptimizeNoopCopyExpression(CI, *TLI)) 9171a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return true; 918c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 9191a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (isa<ZExtInst>(I) || isa<SExtInst>(I)) { 9201a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner bool MadeChange = MoveExtToFormExtLoad(I); 9211a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return MadeChange | OptimizeExtUses(I); 922c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } 9231a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 9241a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner } 9251a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 9261a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (CmpInst *CI = dyn_cast<CmpInst>(I)) 9271a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return OptimizeCmpExpression(CI); 9281a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 9291a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 930c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (TLI) 9311a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return OptimizeMemoryInst(I, I->getOperand(0), LI->getType()); 9321a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 9331a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner } 9341a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 9351a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 936c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (TLI) 9371a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return OptimizeMemoryInst(I, SI->getOperand(1), 9381a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner SI->getOperand(0)->getType()); 9391a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 9401a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner } 9411a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 9421a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 943865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich if (GEPI->hasAllZeroIndices()) { 944865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich /// The GEP operand must be a pointer, so must its result -> BitCast 945865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 946865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich GEPI->getName(), GEPI); 947865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich GEPI->replaceAllUsesWith(NC); 948865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich GEPI->eraseFromParent(); 949865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich ++NumGEPsElim; 950865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich OptimizeInst(NC); 9511a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return true; 952865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich } 9531a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 954c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } 9551a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 9561a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (CallInst *CI = dyn_cast<CallInst>(I)) 9571a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return OptimizeCallInst(CI); 958c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 9591a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 960c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich} 961c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 962dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// In this pass we look for GEP and cast instructions that are used 963dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// across basic blocks and rewrite them to improve basic-block-at-a-time 964dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// selection. 965dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { 9668c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich SunkAddrs.clear(); 96756e3793acf8099eafa36154d2b6c900d46b5965eCameron Zwarich bool MadeChange = false; 968692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 9697579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner CurInstIterator = BB.begin(); 97094e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner for (BasicBlock::iterator E = BB.end(); CurInstIterator != E; ) 97194e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner MadeChange |= OptimizeInst(CurInstIterator++); 972692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 973dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 974dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 975