CodeGenPrepare.cpp revision bdcb726fcad1e3fddc70847a2b91d4d4f9396938
1dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner//===- CodeGenPrepare.cpp - Prepare a function for code generation --------===// 2dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// 3dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// The LLVM Compiler Infrastructure 4dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// 5dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// This file was developed by Chris Lattner and is distributed under 6dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// the University of Illinois Open Source 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 11dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// SelectionDAG-based code generation. This works around limitations in it's 12dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// 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" 21dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Instructions.h" 22dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Pass.h" 23dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetAsmInfo.h" 24dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetData.h" 25dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetLowering.h" 26dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetMachine.h" 27dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 28dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Transforms/Utils/Local.h" 29dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/ADT/DenseMap.h" 30dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/ADT/SmallSet.h" 31bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng#include "llvm/Support/CommandLine.h" 32d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner#include "llvm/Support/Compiler.h" 33bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng#include "llvm/Support/Debug.h" 34dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 35dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerusing namespace llvm; 36dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 37bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Chengnamespace { 38bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng cl::opt<bool> OptExtUses("optimize-ext-uses", 39bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng cl::init(false), cl::Hidden); 40bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng} 41bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 42dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnernamespace { 43dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner class VISIBILITY_HIDDEN CodeGenPrepare : public FunctionPass { 44dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// TLI - Keep a pointer of a TargetLowering to consult for determining 45dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// transformation profitability. 46dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner const TargetLowering *TLI; 47dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner public: 48ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 49c2bbfc18e9adbbdcf5b3375d8d25e2452f7df7f1Dan Gohman explicit CodeGenPrepare(const TargetLowering *tli = 0) 50c2bbfc18e9adbbdcf5b3375d8d25e2452f7df7f1Dan Gohman : FunctionPass((intptr_t)&ID), TLI(tli) {} 51dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool runOnFunction(Function &F); 52dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 53dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner private: 54d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool EliminateMostlyEmptyBlocks(Function &F); 55d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; 56d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner void EliminateMostlyEmptyBlock(BasicBlock *BB); 57dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool OptimizeBlock(BasicBlock &BB); 58dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool OptimizeLoadStoreInst(Instruction *I, Value *Addr, 59dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const Type *AccessTy, 60dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DenseMap<Value*,Value*> &SunkAddrs); 61bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool OptimizeExtUses(Instruction *I); 62dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner }; 63dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 64794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 651997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar CodeGenPrepare::ID = 0; 66dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerstatic RegisterPass<CodeGenPrepare> X("codegenprepare", 67dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner "Optimize for code generation"); 68dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 69dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris LattnerFunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { 70dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return new CodeGenPrepare(TLI); 71dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 72dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 73dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 74dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::runOnFunction(Function &F) { 75dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool EverMadeChange = false; 76d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 77d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // First pass, eliminate blocks that contain only PHI nodes and an 78d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // unconditional branch. 79d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EverMadeChange |= EliminateMostlyEmptyBlocks(F); 80d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 81d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = true; 82dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner while (MadeChange) { 83dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = false; 84dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 85dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange |= OptimizeBlock(*BB); 86dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner EverMadeChange |= MadeChange; 87dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 88dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return EverMadeChange; 89dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 90dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 91d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes 92d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// and an unconditional branch. Passes before isel (e.g. LSR/loopsimplify) 93d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// often split edges in ways that are non-optimal for isel. Start by 94d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// eliminating these blocks so we can split them the way we want them. 95d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) { 96d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = false; 97d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Note that this intentionally skips the entry block. 98d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) { 99d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *BB = I++; 100d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 101d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If this block doesn't end with an uncond branch, ignore it. 102d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 103d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!BI || !BI->isUnconditional()) 104d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 105d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 106d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If the instruction before the branch isn't a phi node, then other stuff 107d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // is happening here. 108d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::iterator BBI = BI; 109d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBI != BB->begin()) { 110d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner --BBI; 111d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!isa<PHINode>(BBI)) continue; 112d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 113d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 114d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Do not break infinite loops. 115d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 116d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (DestBB == BB) 117d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 118d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 119d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!CanMergeBlocks(BB, DestBB)) 120d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 121d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 122d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EliminateMostlyEmptyBlock(BB); 123d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner MadeChange = true; 124d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 125d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return MadeChange; 126d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 127d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 128d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a 129d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// single uncond branch between them, and BB contains no other non-phi 130d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// instructions. 131d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, 132d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const BasicBlock *DestBB) const { 133d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // We only want to eliminate blocks whose phi nodes are used by phi nodes in 134d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // the successor. If there are more complex condition (e.g. preheaders), 135d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // don't mess around with them. 136d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::const_iterator BBI = BB->begin(); 137d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 138d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (Value::use_const_iterator UI = PN->use_begin(), E = PN->use_end(); 139d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner UI != E; ++UI) { 140d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Instruction *User = cast<Instruction>(*UI); 141d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (User->getParent() != DestBB || !isa<PHINode>(User)) 142d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return false; 14375abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel // If User is inside DestBB block and it is a PHINode then check 14475abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel // incoming value. If incoming value is not from BB then this is 14575abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel // a complex condition (e.g. preheaders) we want to avoid here. 14675abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (User->getParent() == DestBB) { 14775abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (const PHINode *UPN = dyn_cast<PHINode>(User)) 14875abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { 14975abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); 15075abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (Insn && Insn->getParent() == BB && 15175abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Insn->getParent() != UPN->getIncomingBlock(I)) 15275abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel return false; 15375abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 15475abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 155d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 156d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 157d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 158d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If BB and DestBB contain any common predecessors, then the phi nodes in BB 159d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // and DestBB may have conflicting incoming values for the block. If so, we 160d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // can't merge the block. 161d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); 162d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!DestBBPN) return true; // no conflict. 163d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 164d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Collect the preds of BB. 165f67f73a519eac94b6c1f98dbce7d251a3a4aea07Chris Lattner SmallPtrSet<const BasicBlock*, 16> BBPreds; 166d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 167d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // It is faster to get preds from a PHI than with pred_iterator. 168d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 169d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(BBPN->getIncomingBlock(i)); 170d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 171d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(pred_begin(BB), pred_end(BB)); 172d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 173d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 174d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Walk the preds of DestBB. 175d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { 176d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *Pred = DestBBPN->getIncomingBlock(i); 177d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBPreds.count(Pred)) { // Common predecessor? 178d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBI = DestBB->begin(); 179d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 180d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V1 = PN->getIncomingValueForBlock(Pred); 181d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V2 = PN->getIncomingValueForBlock(BB); 182d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 183d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If V2 is a phi node in BB, look up what the mapped value will be. 184d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) 185d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V2PN->getParent() == BB) 186d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner V2 = V2PN->getIncomingValueForBlock(Pred); 187d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 188d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If there is a conflict, bail out. 189d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V1 != V2) return false; 190d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 191d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 192d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 193d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 194d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return true; 195d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 196d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 197d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 198d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and 199d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// an unconditional branch in it. 200d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnervoid CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { 201d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 202d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 203d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 204d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner DOUT << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB; 205d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 206d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If the destination block has a single pred, then this is a trivial edge, 207d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // just collapse it. 208d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (DestBB->getSinglePredecessor()) { 209d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If DestBB has single-entry PHI nodes, fold them. 210d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 211d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 212d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->eraseFromParent(); 213d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 214d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 215d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Splice all the PHI nodes from BB over to DestBB. 216d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner DestBB->getInstList().splice(DestBB->begin(), BB->getInstList(), 217d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->begin(), BI); 218d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 219d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Anything that branched to BB now branches to DestBB. 220d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->replaceAllUsesWith(DestBB); 221d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 222d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Nuke BB. 223d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->eraseFromParent(); 224d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 225d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner DOUT << "AFTER:\n" << *DestBB << "\n\n\n"; 226d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return; 227d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 228d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 229d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB 230d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // to handle the new incoming edges it is about to have. 231d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *PN; 232d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (BasicBlock::iterator BBI = DestBB->begin(); 233d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 234d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Remove the incoming value for BB, and remember it. 235d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner Value *InVal = PN->removeIncomingValue(BB, false); 236d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 237d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Two options: either the InVal is a phi node defined in BB or it is some 238d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // value that dominates BB. 239d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *InValPhi = dyn_cast<PHINode>(InVal); 240d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (InValPhi && InValPhi->getParent() == BB) { 241d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Add all of the input values of the input PHI as inputs of this phi. 242d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) 243d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InValPhi->getIncomingValue(i), 244d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner InValPhi->getIncomingBlock(i)); 245d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 246d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, add one instance of the dominating value for each edge that 247d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // we will be adding. 248d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 249d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 250d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); 251d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 252d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 253d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, *PI); 254d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 255d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 256d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 257d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 258d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // The PHIs are now updated, change everything that refers to BB to use 259d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // DestBB and remove BB. 260d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->replaceAllUsesWith(DestBB); 261d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->eraseFromParent(); 262d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 263d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner DOUT << "AFTER:\n" << *DestBB << "\n\n\n"; 264d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 265d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 266d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 267dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// SplitEdgeNicely - Split the critical edge from TI to it's specified 268dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// successor if it will improve codegen. We only do this if the successor has 269dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// phi nodes (otherwise critical edges are ok). If there is already another 270dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// predecessor of the succ that is empty (and thus has no phi nodes), use it 271dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// instead of introducing a new block. 272dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerstatic void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, Pass *P) { 273dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *TIBB = TI->getParent(); 274dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *Dest = TI->getSuccessor(SuccNum); 275dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner assert(isa<PHINode>(Dest->begin()) && 276dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner "This should only be called if Dest has a PHI!"); 277dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 278dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// TIPHIValues - This array is lazily computed to determine the values of 279dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// PHIs in Dest that TI would provide. 280dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner std::vector<Value*> TIPHIValues; 281dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 282dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Check to see if Dest has any blocks that can be used as a split edge for 283dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // this terminator. 284dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (pred_iterator PI = pred_begin(Dest), E = pred_end(Dest); PI != E; ++PI) { 285dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *Pred = *PI; 286dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // To be usable, the pred has to end with an uncond branch to the dest. 287dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator()); 288dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (!PredBr || !PredBr->isUnconditional() || 289dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Must be empty other than the branch. 2906603a1bff0e25e1d9f7be08c65c7b584c7bb84d7Dale Johannesen &Pred->front() != PredBr || 2916603a1bff0e25e1d9f7be08c65c7b584c7bb84d7Dale Johannesen // Cannot be the entry block; its label does not get emitted. 2926603a1bff0e25e1d9f7be08c65c7b584c7bb84d7Dale Johannesen Pred == &(Dest->getParent()->getEntryBlock())) 293dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner continue; 294dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 295dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Finally, since we know that Dest has phi nodes in it, we have to make 296dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // sure that jumping to Pred will have the same affect as going to Dest in 297dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // terms of PHI values. 298dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner PHINode *PN; 299dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner unsigned PHINo = 0; 300dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool FoundMatch = true; 301dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (BasicBlock::iterator I = Dest->begin(); 302dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) { 303dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (PHINo == TIPHIValues.size()) 304dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TIPHIValues.push_back(PN->getIncomingValueForBlock(TIBB)); 305dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 306dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If the PHI entry doesn't work, we can't use this pred. 307dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (TIPHIValues[PHINo] != PN->getIncomingValueForBlock(Pred)) { 308dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner FoundMatch = false; 309dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner break; 310dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 311dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 312dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 313dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we found a workable predecessor, change TI to branch to Succ. 314dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (FoundMatch) { 315dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Dest->removePredecessor(TIBB); 316dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TI->setSuccessor(SuccNum, Pred); 317dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return; 318dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 319dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 320dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 321dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner SplitCriticalEdge(TI, SuccNum, P, true); 322dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 323dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 324dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// OptimizeNoopCopyExpression - If the specified cast instruction is a noop 325dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// copy (e.g. it's casting from one pointer type to another, int->uint, or 326dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// int->sbyte on PPC), 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. 330dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){ 331dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is a noop copy, 332dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner MVT::ValueType SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 333dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner MVT::ValueType DstVT = TLI.getValueType(CI->getType()); 334dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 335dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This is an fp<->int conversion? 336dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (MVT::isInteger(SrcVT) != MVT::isInteger(DstVT)) 337dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 338dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 339dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is an extension, it will be a zero or sign extension, which 340dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // isn't a noop. 341dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SrcVT < DstVT) return false; 342dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 343dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If these values will be promoted, find out what they will be promoted 344dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // to. This helps us consider truncates on PPC as noop copies when they 345dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // are. 346dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) 347dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SrcVT = TLI.getTypeToTransformTo(SrcVT); 348dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.getTypeAction(DstVT) == TargetLowering::Promote) 349dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DstVT = TLI.getTypeToTransformTo(DstVT); 350dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 351dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If, after promotion, these are the same types, this is a noop copy. 352dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SrcVT != DstVT) 353dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 354dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 355dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *DefBB = CI->getParent(); 356dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 357dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// InsertedCasts - Only insert a cast in each block once. 358ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CastInst*> InsertedCasts; 359dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 360dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 361dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 362dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner UI != E; ) { 363dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Use &TheUse = UI.getUse(); 364dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *User = cast<Instruction>(*UI); 365dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 366dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Figure out which BB this cast is used in. For PHI's this is the 367dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // appropriate predecessor block. 368dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *UserBB = User->getParent(); 369dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) { 370dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner unsigned OpVal = UI.getOperandNo()/2; 371dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner UserBB = PN->getIncomingBlock(OpVal); 372dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 373dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 374dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Preincrement use iterator so we don't invalidate it. 375dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner ++UI; 376dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 377dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If this user is in the same block as the cast, don't change the cast. 378dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (UserBB == DefBB) continue; 379dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 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) { 384dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock::iterator InsertPt = UserBB->begin(); 385dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner while (isa<PHINode>(InsertPt)) ++InsertPt; 386dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 387dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner InsertedCast = 388dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CastInst::create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 389dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner InsertPt); 390dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = true; 391dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 392dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 393ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cast with a use of the new cast. 394dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TheUse = InsertedCast; 395dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 396dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 397dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we removed all uses, nuke the cast. 398dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (CI->use_empty()) 399dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CI->eraseFromParent(); 400dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 401dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 402dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 403dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 404ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce 405ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// the number of virtual registers that must be created and coalesced. This is 406684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// a clear win except on targets with multiple condition code registers 407684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// (PowerPC), where it might lose; some adjustment may be wanted there. 408ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// 409ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// Return true if any changes are made. 410ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesenstatic bool OptimizeCmpExpression(CmpInst *CI){ 411ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 412ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *DefBB = CI->getParent(); 413ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 414ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen /// InsertedCmp - Only insert a cmp in each block once. 415ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CmpInst*> InsertedCmps; 416ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 417ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen bool MadeChange = false; 418ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 419ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen UI != E; ) { 420ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Use &TheUse = UI.getUse(); 421ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Instruction *User = cast<Instruction>(*UI); 422ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 423ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Preincrement use iterator so we don't invalidate it. 424ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen ++UI; 425ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 426ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Don't bother for PHI nodes. 427ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (isa<PHINode>(User)) 428ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen continue; 429ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 430ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Figure out which BB this cmp is used in. 431ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *UserBB = User->getParent(); 432ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 433ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If this user is in the same block as the cmp, don't change the cmp. 434ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (UserBB == DefBB) continue; 435ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 436ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we have already inserted a cmp into this block, use it. 437ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CmpInst *&InsertedCmp = InsertedCmps[UserBB]; 438ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 439ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (!InsertedCmp) { 440ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock::iterator InsertPt = UserBB->begin(); 441ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen while (isa<PHINode>(InsertPt)) ++InsertPt; 442ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 443ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen InsertedCmp = 444ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CmpInst::create(CI->getOpcode(), CI->getPredicate(), CI->getOperand(0), 445ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->getOperand(1), "", InsertPt); 446ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen MadeChange = true; 447ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 448ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 449ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cmp with a use of the new cmp. 450ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen TheUse = InsertedCmp; 451ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 452ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 453ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we removed all uses, nuke the cmp. 454ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (CI->use_empty()) 455ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->eraseFromParent(); 456ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 457ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen return MadeChange; 458ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen} 459ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 460dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// EraseDeadInstructions - Erase any dead instructions 461dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic void EraseDeadInstructions(Value *V) { 462dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Instruction *I = dyn_cast<Instruction>(V); 463dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!I || !I->use_empty()) return; 464dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 465dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SmallPtrSet<Instruction*, 16> Insts; 466dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Insts.insert(I); 467dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 468dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner while (!Insts.empty()) { 469dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner I = *Insts.begin(); 470dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Insts.erase(I); 471dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (isInstructionTriviallyDead(I)) { 472dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 473dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i))) 474dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Insts.insert(U); 475dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner I->eraseFromParent(); 476dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 477dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 478dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 479dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 480dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 481dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// ExtAddrMode - This is an extended version of TargetLowering::AddrMode which 482dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// holds actual Value*'s for register values. 483dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstruct ExtAddrMode : public TargetLowering::AddrMode { 484dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *BaseReg; 485dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *ScaledReg; 486dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ExtAddrMode() : BaseReg(0), ScaledReg(0) {} 487dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner void dump() const; 488dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner}; 489dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 490dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic std::ostream &operator<<(std::ostream &OS, const ExtAddrMode &AM) { 491dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool NeedPlus = false; 492dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner OS << "["; 493dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AM.BaseGV) 494dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner OS << (NeedPlus ? " + " : "") 495dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner << "GV:%" << AM.BaseGV->getName(), NeedPlus = true; 496dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 497dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AM.BaseOffs) 498dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner OS << (NeedPlus ? " + " : "") << AM.BaseOffs, NeedPlus = true; 499dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 500dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AM.BaseReg) 501dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner OS << (NeedPlus ? " + " : "") 502dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner << "Base:%" << AM.BaseReg->getName(), NeedPlus = true; 503dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AM.Scale) 504dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner OS << (NeedPlus ? " + " : "") 505dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner << AM.Scale << "*%" << AM.ScaledReg->getName(), NeedPlus = true; 506dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 507dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return OS << "]"; 508dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 509dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 510dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnervoid ExtAddrMode::dump() const { 511dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cerr << *this << "\n"; 512dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 513dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 514dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool TryMatchingScaledValue(Value *ScaleReg, int64_t Scale, 515dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const Type *AccessTy, ExtAddrMode &AddrMode, 516dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SmallVector<Instruction*, 16> &AddrModeInsts, 517dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const TargetLowering &TLI, unsigned Depth); 518dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 519dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// FindMaximalLegalAddressingMode - If we can, try to merge the computation of 520dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// Addr into the specified addressing mode. If Addr can't be added to AddrMode 521dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// this returns false. This assumes that Addr is either a pointer type or 522dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// intptr_t for the target. 523dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool FindMaximalLegalAddressingMode(Value *Addr, const Type *AccessTy, 524dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ExtAddrMode &AddrMode, 525dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SmallVector<Instruction*, 16> &AddrModeInsts, 526dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const TargetLowering &TLI, 527dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner unsigned Depth) { 528dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 529dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is a global variable, fold it into the addressing mode if possible. 530dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (GlobalValue *GV = dyn_cast<GlobalValue>(Addr)) { 531dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseGV == 0) { 532dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseGV = GV; 533dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 534dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 535dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseGV = 0; 536dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 537dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (ConstantInt *CI = dyn_cast<ConstantInt>(Addr)) { 538dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseOffs += CI->getSExtValue(); 539dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 540dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 541dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseOffs -= CI->getSExtValue(); 542dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (isa<ConstantPointerNull>(Addr)) { 543dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 544dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 545dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 546dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Look through constant exprs and instructions. 547dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner unsigned Opcode = ~0U; 548dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner User *AddrInst = 0; 549dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast<Instruction>(Addr)) { 550dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Opcode = I->getOpcode(); 551dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrInst = I; 552dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) { 553dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Opcode = CE->getOpcode(); 554dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrInst = CE; 555dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 556dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 557dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Limit recursion to avoid exponential behavior. 558dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Depth == 5) { AddrInst = 0; Opcode = ~0U; } 559dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 560dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is really an instruction, add it to our list of related 561dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // instructions. 562dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast_or_null<Instruction>(AddrInst)) 563dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts.push_back(I); 564dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 565dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner switch (Opcode) { 566dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::PtrToInt: 567dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // PtrToInt is always a noop, as we know that the int type is pointer sized. 568dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, 569dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, Depth)) 570dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 571dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 572dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::IntToPtr: 573dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This inttoptr is a no-op if the integer type is pointer sized. 574dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.getValueType(AddrInst->getOperand(0)->getType()) == 575dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner TLI.getPointerTy()) { 576dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, 577dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, Depth)) 578dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 579dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 580dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 581dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::Add: { 582dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if we can merge in the RHS then the LHS. If so, we win. 583dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ExtAddrMode BackupAddrMode = AddrMode; 584dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner unsigned OldSize = AddrModeInsts.size(); 585dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (FindMaximalLegalAddressingMode(AddrInst->getOperand(1), AccessTy, 586dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, Depth+1) && 587dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, 588dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, Depth+1)) 589dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 590dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 591dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Restore the old addr mode info. 592dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode = BackupAddrMode; 593dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts.resize(OldSize); 594dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 595dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Otherwise this was over-aggressive. Try merging in the LHS then the RHS. 596dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, 597dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, Depth+1) && 598dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner FindMaximalLegalAddressingMode(AddrInst->getOperand(1), AccessTy, 599dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, Depth+1)) 600dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 601dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 602dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Otherwise we definitely can't merge the ADD in. 603dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode = BackupAddrMode; 604dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts.resize(OldSize); 605dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 606dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 607dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::Or: { 608dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1)); 609dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!RHS) break; 610dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD. 611dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 612dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 613dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::Mul: 614dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::Shl: { 615dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Can only handle X*C and X << C, and can only handle this when the scale 616dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // field is available. 617dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1)); 618dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!RHS) break; 619dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner int64_t Scale = RHS->getSExtValue(); 620dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Opcode == Instruction::Shl) 621dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Scale = 1 << Scale; 622dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 623dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TryMatchingScaledValue(AddrInst->getOperand(0), Scale, AccessTy, 624dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, Depth)) 625dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 626dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 627dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 628dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner case Instruction::GetElementPtr: { 629dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Scan the GEP. We check it if it contains constant offsets and at most 630dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // one variable offset. 631dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner int VariableOperand = -1; 632dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner unsigned VariableScale = 0; 633dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 634dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner int64_t ConstantOffset = 0; 635dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const TargetData *TD = TLI.getTargetData(); 636dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner gep_type_iterator GTI = gep_type_begin(AddrInst); 637dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) { 638dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (const StructType *STy = dyn_cast<StructType>(*GTI)) { 639dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const StructLayout *SL = TD->getStructLayout(STy); 640dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner unsigned Idx = 641dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue(); 642dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ConstantOffset += SL->getElementOffset(Idx); 643dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 644514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands uint64_t TypeSize = TD->getABITypeSize(GTI.getIndexedType()); 645dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(AddrInst->getOperand(i))) { 646dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ConstantOffset += CI->getSExtValue()*TypeSize; 647dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (TypeSize) { // Scales of zero don't do anything. 648dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // We only allow one variable index at the moment. 649dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (VariableOperand != -1) { 650dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner VariableOperand = -2; 651dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 652dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 653dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 654dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Remember the variable index. 655dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner VariableOperand = i; 656dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner VariableScale = TypeSize; 657dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 658dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 659dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 660dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 661dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If the GEP had multiple variable indices, punt. 662dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (VariableOperand == -2) 663dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 664dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 665dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // A common case is for the GEP to only do a constant offset. In this case, 666dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // just add it to the disp field and check validity. 667dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (VariableOperand == -1) { 668dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseOffs += ConstantOffset; 669dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (ConstantOffset == 0 || TLI.isLegalAddressingMode(AddrMode, AccessTy)){ 670dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if we can fold the base pointer in too. 671dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, 672dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, 673dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Depth+1)) 674dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 675dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 676dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseOffs -= ConstantOffset; 677dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 678dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check that this has no base reg yet. If so, we won't have a place to 679dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // put the base of the GEP (assuming it is not a null ptr). 680dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool SetBaseReg = false; 681dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.HasBaseReg) { 682dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!isa<ConstantPointerNull>(AddrInst->getOperand(0))) 683dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 684dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 685dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.HasBaseReg = true; 686dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseReg = AddrInst->getOperand(0); 687dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SetBaseReg = true; 688dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 689dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 690dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // See if the scale amount is valid for this target. 691dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseOffs += ConstantOffset; 692dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TryMatchingScaledValue(AddrInst->getOperand(VariableOperand), 693dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner VariableScale, AccessTy, AddrMode, 694dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts, TLI, Depth)) { 695dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!SetBaseReg) return true; 696dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 697dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this match succeeded, we know that we can form an address with the 698dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // GepBase as the basereg. See if we can match *more*. 699dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.HasBaseReg = false; 700dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseReg = 0; 701dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, 702dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode, AddrModeInsts, TLI, 703dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Depth+1)) 704dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 705dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Strange, shouldn't happen. Restore the base reg and succeed the easy 706dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // way. 707dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.HasBaseReg = true; 708dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseReg = AddrInst->getOperand(0); 709dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 710dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 711dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 712dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseOffs -= ConstantOffset; 713dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SetBaseReg) { 714dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.HasBaseReg = false; 715dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseReg = 0; 716dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 717dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 718dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 719dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 720dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 721dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 722dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast_or_null<Instruction>(AddrInst)) { 723dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner assert(AddrModeInsts.back() == I && "Stack imbalance"); 724dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts.pop_back(); 725dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 726dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 727dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Worse case, the target should support [reg] addressing modes. :) 728dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!AddrMode.HasBaseReg) { 729dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.HasBaseReg = true; 730dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Still check for legality in case the target supports [imm] but not [i+r]. 731dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) { 732dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.BaseReg = Addr; 733dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 734dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 735dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.HasBaseReg = false; 736dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 737dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 738dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If the base register is already taken, see if we can do [r+r]. 739dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale == 0) { 740dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.Scale = 1; 741dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) { 742dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.ScaledReg = Addr; 743dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 744dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 745dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.Scale = 0; 746dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 747dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Couldn't match. 748dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 749dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 750dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 751dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// TryMatchingScaledValue - Try adding ScaleReg*Scale to the specified 752dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// addressing mode. Return true if this addr mode is legal for the target, 753dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// false if not. 754dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool TryMatchingScaledValue(Value *ScaleReg, int64_t Scale, 755dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const Type *AccessTy, ExtAddrMode &AddrMode, 756dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SmallVector<Instruction*, 16> &AddrModeInsts, 757dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const TargetLowering &TLI, unsigned Depth) { 758dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If we already have a scale of this value, we can add to it, otherwise, we 759dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // need an available scale field. 760dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg) 761dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 762dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 763dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ExtAddrMode InputAddrMode = AddrMode; 764dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 765dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add scale to turn X*4+X*3 -> X*7. This could also do things like 766dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // [A+B + A*7] -> [B+A*8]. 767dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.Scale += Scale; 768dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.ScaledReg = ScaleReg; 769dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 770dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) { 771dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Okay, we decided that we can add ScaleReg+Scale to AddrMode. Check now 772dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // to see if ScaleReg is actually X+C. If so, we can turn this into adding 773dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // X*Scale + C*Scale to addr mode. 774dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner BinaryOperator *BinOp = dyn_cast<BinaryOperator>(ScaleReg); 775dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (BinOp && BinOp->getOpcode() == Instruction::Add && 776dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner isa<ConstantInt>(BinOp->getOperand(1)) && InputAddrMode.ScaledReg ==0) { 777dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 778dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner InputAddrMode.Scale = Scale; 779dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner InputAddrMode.ScaledReg = BinOp->getOperand(0); 780dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner InputAddrMode.BaseOffs += 781dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cast<ConstantInt>(BinOp->getOperand(1))->getSExtValue()*Scale; 782dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI.isLegalAddressingMode(InputAddrMode, AccessTy)) { 783dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts.push_back(BinOp); 784dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode = InputAddrMode; 785dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 786dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 787dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 788dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 789dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Otherwise, not (x+c)*scale, just return what we have. 790dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 791dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 792dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 793dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Otherwise, back this attempt out. 794dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.Scale -= Scale; 795dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale == 0) AddrMode.ScaledReg = 0; 796dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 797dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 798dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 799dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 800dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 801dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// IsNonLocalValue - Return true if the specified values are defined in a 802dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// different basic block than BB. 803dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool IsNonLocalValue(Value *V, BasicBlock *BB) { 804dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 805dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return I->getParent() != BB; 806dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 807dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 808dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 809dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// OptimizeLoadStoreInst - Load and Store Instructions have often have 810dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// addressing modes that can do significant amounts of computation. As such, 811dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// instruction selection will try to get the load or store to do as much 812dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// computation as possible for the program. The problem is that isel can only 813dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// see within a single block. As such, we sink as much legal addressing mode 814dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// stuff into the block as possible. 815dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerbool CodeGenPrepare::OptimizeLoadStoreInst(Instruction *LdStInst, Value *Addr, 816dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const Type *AccessTy, 817dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DenseMap<Value*,Value*> &SunkAddrs) { 818dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Figure out what addressing mode will be built up for this operation. 819dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SmallVector<Instruction*, 16> AddrModeInsts; 820dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner ExtAddrMode AddrMode; 821dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool Success = FindMaximalLegalAddressingMode(Addr, AccessTy, AddrMode, 822dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrModeInsts, *TLI, 0); 823dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Success = Success; assert(Success && "Couldn't select *anything*?"); 824dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 825dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if any of the instructions supersumed by this addr mode are 826dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // non-local to I's BB. 827dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool AnyNonLocal = false; 828dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { 829dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (IsNonLocalValue(AddrModeInsts[i], LdStInst->getParent())) { 830dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AnyNonLocal = true; 831dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 832dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 833dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 834dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 835dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If all the instructions matched are already in this BB, don't do anything. 836dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!AnyNonLocal) { 837dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DEBUG(cerr << "CGP: Found local addrmode: " << AddrMode << "\n"); 838dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 839dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 840dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 841dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Insert this computation right after this user. Since our caller is 842dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // scanning from the top of the BB to the bottom, reuse of the expr are 843dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // guaranteed to happen later. 844dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner BasicBlock::iterator InsertPt = LdStInst; 845dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 846dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Now that we determined the addressing expression we want to use and know 847dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // that we have to sink it into this block. Check to see if we have already 848dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done this for some other load/store instr in this block. If so, reuse the 849dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // computation. 850dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *&SunkAddr = SunkAddrs[Addr]; 851dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr) { 852dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DEBUG(cerr << "CGP: Reusing nonlocal addrmode: " << AddrMode << "\n"); 853dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr->getType() != Addr->getType()) 854dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new BitCastInst(SunkAddr, Addr->getType(), "tmp", InsertPt); 855dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 856dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DEBUG(cerr << "CGP: SINKING nonlocal addrmode: " << AddrMode << "\n"); 857dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner const Type *IntPtrTy = TLI->getTargetData()->getIntPtrType(); 858dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 859dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *Result = 0; 860dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Start with the scale value. 861dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale) { 862dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = AddrMode.ScaledReg; 863dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (V->getType() == IntPtrTy) { 864dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done. 865dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (isa<PointerType>(V->getType())) { 866dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 867dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 868dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cast<IntegerType>(V->getType())->getBitWidth()) { 869dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new TruncInst(V, IntPtrTy, "sunkaddr", InsertPt); 870dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 871dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new SExtInst(V, IntPtrTy, "sunkaddr", InsertPt); 872dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 873dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale != 1) 874dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = BinaryOperator::createMul(V, ConstantInt::get(IntPtrTy, 875dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AddrMode.Scale), 876dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner "sunkaddr", InsertPt); 877dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 878dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 879dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 880dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the base register. 881dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseReg) { 882dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = AddrMode.BaseReg; 883dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (V->getType() != IntPtrTy) 884dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 885dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 886dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = BinaryOperator::createAdd(Result, V, "sunkaddr", InsertPt); 887dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 888dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 889dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 890dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 891dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the BaseGV if present. 892dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseGV) { 893dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = new PtrToIntInst(AddrMode.BaseGV, IntPtrTy, "sunkaddr", 894dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner InsertPt); 895dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 896dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = BinaryOperator::createAdd(Result, V, "sunkaddr", InsertPt); 897dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 898dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 899dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 900dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 901dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the Base Offset if present. 902dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseOffs) { 903dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 904dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 905dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = BinaryOperator::createAdd(Result, V, "sunkaddr", InsertPt); 906dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 907dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 908dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 909dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 910dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result == 0) 911dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = Constant::getNullValue(Addr->getType()); 912dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 913dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new IntToPtrInst(Result, Addr->getType(), "sunkaddr",InsertPt); 914dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 915dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 916dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner LdStInst->replaceUsesOfWith(Addr, SunkAddr); 917dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 918dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Addr->use_empty()) 919dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner EraseDeadInstructions(Addr); 920dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 921dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 922dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 923bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Chengbool CodeGenPrepare::OptimizeExtUses(Instruction *I) { 924bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *DefBB = I->getParent(); 925bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 926bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // If both result of the {s|z}xt and its source are live out, rewrite all 927bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // other uses of the source with result of extension. 928bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Value *Src = I->getOperand(0); 929bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (Src->hasOneUse()) 930bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 931bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 932bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool DefIsLiveOut = false; 933bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 934bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 935bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 936bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 937bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 938bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 939bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 940bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DefIsLiveOut = true; 941bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng break; 942bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 943bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!DefIsLiveOut) 944bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 945bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 946bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // InsertedTruncs - Only insert one trunc in each block once. 947bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DenseMap<BasicBlock*, Instruction*> InsertedTruncs; 948bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 949bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool MadeChange = false; 950bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 951bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 952bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Use &TheUse = UI.getUse(); 953bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 954bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 955bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 956bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 957bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 958bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 959bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Both src and def are live in this block. Rewrite the use. 960bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *&InsertedTrunc = InsertedTruncs[UserBB]; 961bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 962bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!InsertedTrunc) { 963bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock::iterator InsertPt = UserBB->begin(); 964bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng while (isa<PHINode>(InsertPt)) ++InsertPt; 965bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 966bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt); 967bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 968bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 969bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Replace a use of the {s|z}ext source with a use of the result. 970bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng TheUse = InsertedTrunc; 971bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 972bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange = true; 973bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 974bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 975bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return MadeChange; 976bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng} 977bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 978dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// In this pass we look for GEP and cast instructions that are used 979dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// across basic blocks and rewrite them to improve basic-block-at-a-time 980dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// selection. 981dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { 982dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 983dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 984dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Split all critical edges where the dest block has a PHI and where the phi 985dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // has shared immediate operands. 986dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TerminatorInst *BBTI = BB.getTerminator(); 987dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (BBTI->getNumSuccessors() > 1) { 988dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (unsigned i = 0, e = BBTI->getNumSuccessors(); i != e; ++i) 989dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (isa<PHINode>(BBTI->getSuccessor(i)->begin()) && 990dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner isCriticalEdge(BBTI, i, true)) 991dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner SplitEdgeNicely(BBTI, i, this); 992dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 993dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 994dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 995dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Keep track of non-local addresses that have been sunk into this block. 996dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This allows us to avoid inserting duplicate code for blocks with multiple 997dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // load/stores of the same address. 998dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner DenseMap<Value*, Value*> SunkAddrs; 999dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 1000dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (BasicBlock::iterator BBI = BB.begin(), E = BB.end(); BBI != E; ) { 1001dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *I = BBI++; 1002dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 1003dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (CastInst *CI = dyn_cast<CastInst>(I)) { 1004dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If the source of the cast is a constant, then this should have 1005dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // already been constant folded. The only reason NOT to constant fold 1006dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // it is if something (e.g. LSR) was careful to place the constant 1007dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // evaluation in a block other than then one that uses it (e.g. to hoist 1008dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // the address of globals out of a loop). If this is the case, we don't 1009dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // want to forward-subst the cast. 1010dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (isa<Constant>(CI->getOperand(0))) 1011dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner continue; 1012dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 1013bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool Change = false; 1014bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (TLI) { 1015bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Change = OptimizeNoopCopyExpression(CI, *TLI); 1016bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange |= Change; 1017bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 1018bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1019bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (OptExtUses && !Change && (isa<ZExtInst>(I) || isa<SExtInst>(I))) 1020bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange |= OptimizeExtUses(I); 1021ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } else if (CmpInst *CI = dyn_cast<CmpInst>(I)) { 1022ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen MadeChange |= OptimizeCmpExpression(CI); 1023dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 1024dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI) 1025dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner MadeChange |= OptimizeLoadStoreInst(I, I->getOperand(0), LI->getType(), 1026dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddrs); 1027dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 1028dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI) 1029dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner MadeChange |= OptimizeLoadStoreInst(I, SI->getOperand(1), 1030dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SI->getOperand(0)->getType(), 1031dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddrs); 1032dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 1033f25646bfb375b614cddcc8b6fda2b524feae1efaChris Lattner if (GEPI->hasAllZeroIndices()) { 1034dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner /// The GEP operand must be a pointer, so must its result -> BitCast 1035dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 1036dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->getName(), GEPI); 1037dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->replaceAllUsesWith(NC); 1038dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner GEPI->eraseFromParent(); 1039dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner MadeChange = true; 1040dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner BBI = NC; 1041dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 1042dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (CallInst *CI = dyn_cast<CallInst>(I)) { 1043dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If we found an inline asm expession, and if the target knows how to 1044dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // lower it to normal LLVM code, do so now. 1045dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TLI && isa<InlineAsm>(CI->getCalledValue())) 1046dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (const TargetAsmInfo *TAI = 1047dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner TLI->getTargetMachine().getTargetAsmInfo()) { 1048dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (TAI->ExpandInlineAsm(CI)) 1049dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner BBI = BB.begin(); 1050dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 1051dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 1052dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 1053dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 1054dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 1055dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 1056dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 1057