PHITransAddr.cpp revision 618c1dbd293d15ee19f61b1156ab8086ad28311a
1210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner//===- PHITransAddr.cpp - PHI Translation for Addresses -------------------===//
2210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner//
3210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner//                     The LLVM Compiler Infrastructure
4210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner//
5210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner// This file is distributed under the University of Illinois Open Source
6210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner// License. See LICENSE.TXT for details.
7210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner//
8210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner//===----------------------------------------------------------------------===//
9210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner//
10210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner// This file implements the PHITransAddr class.
11210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner//
12210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner//===----------------------------------------------------------------------===//
13210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner
14210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner#include "llvm/Analysis/PHITransAddr.h"
15562b84b3aea359d1f918184e355da82bf05eb290Jay Foad#include "llvm/Constants.h"
169fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner#include "llvm/Instructions.h"
17210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner#include "llvm/Analysis/Dominators.h"
189a8641201b2db8427be2a6531c043f384562c081Chris Lattner#include "llvm/Analysis/InstructionSimplify.h"
192a0f3ccc9c10186309d5d6a0c4cebe8b477f352aDavid Greene#include "llvm/Support/Debug.h"
2088fc03c461276f56a2005808cf10faa4cd857e5cDan Gohman#include "llvm/Support/ErrorHandling.h"
217dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner#include "llvm/Support/raw_ostream.h"
22210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattnerusing namespace llvm;
23210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner
246fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattnerstatic bool CanPHITrans(Instruction *Inst) {
259a8641201b2db8427be2a6531c043f384562c081Chris Lattner  if (isa<PHINode>(Inst) ||
266fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner      isa<GetElementPtrInst>(Inst))
279a8641201b2db8427be2a6531c043f384562c081Chris Lattner    return true;
28ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman
29ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman  if (isa<CastInst>(Inst) &&
30ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman      Inst->isSafeToSpeculativelyExecute())
31ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman    return true;
327feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
3334f849098bfb8850fa34fbd115ba9b2e55c85a32Chris Lattner  if (Inst->getOpcode() == Instruction::Add &&
346fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner      isa<ConstantInt>(Inst->getOperand(1)))
356fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    return true;
367feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
379a8641201b2db8427be2a6531c043f384562c081Chris Lattner  //   cerr << "MEMDEP: Could not PHI translate: " << *Pointer;
389a8641201b2db8427be2a6531c043f384562c081Chris Lattner  //   if (isa<BitCastInst>(PtrInst) || isa<GetElementPtrInst>(PtrInst))
399a8641201b2db8427be2a6531c043f384562c081Chris Lattner  //     cerr << "OP:\t\t\t\t" << *PtrInst->getOperand(0);
409a8641201b2db8427be2a6531c043f384562c081Chris Lattner  return false;
41210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner}
42210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner
437dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattnervoid PHITransAddr::dump() const {
447dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  if (Addr == 0) {
452a0f3ccc9c10186309d5d6a0c4cebe8b477f352aDavid Greene    dbgs() << "PHITransAddr: null\n";
467dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner    return;
477dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  }
482a0f3ccc9c10186309d5d6a0c4cebe8b477f352aDavid Greene  dbgs() << "PHITransAddr: " << *Addr << "\n";
497dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  for (unsigned i = 0, e = InstInputs.size(); i != e; ++i)
502a0f3ccc9c10186309d5d6a0c4cebe8b477f352aDavid Greene    dbgs() << "  Input #" << i << " is " << *InstInputs[i] << "\n";
517dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner}
527dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner
537dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner
547dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattnerstatic bool VerifySubExpr(Value *Expr,
557dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner                          SmallVectorImpl<Instruction*> &InstInputs) {
567dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  // If this is a non-instruction value, there is nothing to do.
577dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  Instruction *I = dyn_cast<Instruction>(Expr);
587dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  if (I == 0) return true;
597feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
607dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  // If it's an instruction, it is either in Tmp or its operands recursively
617dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  // are.
627dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  SmallVectorImpl<Instruction*>::iterator Entry =
637dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner    std::find(InstInputs.begin(), InstInputs.end(), I);
647dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  if (Entry != InstInputs.end()) {
657dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner    InstInputs.erase(Entry);
667dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner    return true;
677dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  }
687feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
697dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  // If it isn't in the InstInputs list it is a subexpr incorporated into the
707dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  // address.  Sanity check that it is phi translatable.
717dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  if (!CanPHITrans(I)) {
7288fc03c461276f56a2005808cf10faa4cd857e5cDan Gohman    errs() << "Non phi translatable instruction found in PHITransAddr:\n";
73a8e21d485a71116f187523460efd367763cd8d59David Greene    errs() << *I << '\n';
7488fc03c461276f56a2005808cf10faa4cd857e5cDan Gohman    llvm_unreachable("Either something is missing from InstInputs or "
7588fc03c461276f56a2005808cf10faa4cd857e5cDan Gohman                     "CanPHITrans is wrong.");
767dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner    return false;
777dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  }
787feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
797dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  // Validate the operands of the instruction.
807dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
817dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner    if (!VerifySubExpr(I->getOperand(i), InstInputs))
827dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner      return false;
837dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner
847dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  return true;
857dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner}
867dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner
877dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner/// Verify - Check internal consistency of this data structure.  If the
887dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner/// structure is valid, it returns true.  If invalid, it prints errors and
897dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner/// returns false.
907dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattnerbool PHITransAddr::Verify() const {
917dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  if (Addr == 0) return true;
927feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
937feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman  SmallVector<Instruction*, 8> Tmp(InstInputs.begin(), InstInputs.end());
947feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
957dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  if (!VerifySubExpr(Addr, Tmp))
967dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner    return false;
977feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
987dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  if (!Tmp.empty()) {
9988fc03c461276f56a2005808cf10faa4cd857e5cDan Gohman    errs() << "PHITransAddr contains extra instructions:\n";
1007dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner    for (unsigned i = 0, e = InstInputs.size(); i != e; ++i)
101a8e21d485a71116f187523460efd367763cd8d59David Greene      errs() << "  InstInput #" << i << " is " << *InstInputs[i] << "\n";
10288fc03c461276f56a2005808cf10faa4cd857e5cDan Gohman    llvm_unreachable("This is unexpected.");
1037dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner    return false;
1047dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  }
1057feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
1067dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  // a-ok.
1077dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  return true;
1087dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner}
1097dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner
1107dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner
1116fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner/// IsPotentiallyPHITranslatable - If this needs PHI translation, return true
1126fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner/// if we have some hope of doing it.  This should be used as a filter to
1136fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner/// avoid calling PHITranslateValue in hopeless situations.
1146fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattnerbool PHITransAddr::IsPotentiallyPHITranslatable() const {
1156fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  // If the input value is not an instruction, or if it is not defined in CurBB,
1166fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  // then we don't need to phi translate it.
1176fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  Instruction *Inst = dyn_cast<Instruction>(Addr);
1186fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  return Inst == 0 || CanPHITrans(Inst);
1196fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner}
1206fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner
1219a8641201b2db8427be2a6531c043f384562c081Chris Lattner
1227feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohmanstatic void RemoveInstInputs(Value *V,
12343678f41a37c077f28517c2e4889cca88cada6ceChris Lattner                             SmallVectorImpl<Instruction*> &InstInputs) {
1246200e53f55536f812153ad910e6a69139592301bChris Lattner  Instruction *I = dyn_cast<Instruction>(V);
1256200e53f55536f812153ad910e6a69139592301bChris Lattner  if (I == 0) return;
1267feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
12743678f41a37c077f28517c2e4889cca88cada6ceChris Lattner  // If the instruction is in the InstInputs list, remove it.
12843678f41a37c077f28517c2e4889cca88cada6ceChris Lattner  SmallVectorImpl<Instruction*>::iterator Entry =
12943678f41a37c077f28517c2e4889cca88cada6ceChris Lattner    std::find(InstInputs.begin(), InstInputs.end(), I);
13043678f41a37c077f28517c2e4889cca88cada6ceChris Lattner  if (Entry != InstInputs.end()) {
13143678f41a37c077f28517c2e4889cca88cada6ceChris Lattner    InstInputs.erase(Entry);
13243678f41a37c077f28517c2e4889cca88cada6ceChris Lattner    return;
13343678f41a37c077f28517c2e4889cca88cada6ceChris Lattner  }
1347feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
1356200e53f55536f812153ad910e6a69139592301bChris Lattner  assert(!isa<PHINode>(I) && "Error, removing something that isn't an input");
1367feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
13743678f41a37c077f28517c2e4889cca88cada6ceChris Lattner  // Otherwise, it must have instruction inputs itself.  Zap them recursively.
13843678f41a37c077f28517c2e4889cca88cada6ceChris Lattner  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
1396200e53f55536f812153ad910e6a69139592301bChris Lattner    if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i)))
14043678f41a37c077f28517c2e4889cca88cada6ceChris Lattner      RemoveInstInputs(Op, InstInputs);
14143678f41a37c077f28517c2e4889cca88cada6ceChris Lattner  }
14243678f41a37c077f28517c2e4889cca88cada6ceChris Lattner}
14343678f41a37c077f28517c2e4889cca88cada6ceChris Lattner
1449a8641201b2db8427be2a6531c043f384562c081Chris LattnerValue *PHITransAddr::PHITranslateSubExpr(Value *V, BasicBlock *CurBB,
1456d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar                                         BasicBlock *PredBB,
1466d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar                                         const DominatorTree *DT) {
1479a8641201b2db8427be2a6531c043f384562c081Chris Lattner  // If this is a non-instruction value, it can't require PHI translation.
1489a8641201b2db8427be2a6531c043f384562c081Chris Lattner  Instruction *Inst = dyn_cast<Instruction>(V);
1499a8641201b2db8427be2a6531c043f384562c081Chris Lattner  if (Inst == 0) return V;
1507feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
151af50315a29600188a6ff8b935beca6f1b59edf48Chris Lattner  // Determine whether 'Inst' is an input to our PHI translatable expression.
152af50315a29600188a6ff8b935beca6f1b59edf48Chris Lattner  bool isInput = std::count(InstInputs.begin(), InstInputs.end(), Inst);
153af50315a29600188a6ff8b935beca6f1b59edf48Chris Lattner
154af50315a29600188a6ff8b935beca6f1b59edf48Chris Lattner  // Handle inputs instructions if needed.
155af50315a29600188a6ff8b935beca6f1b59edf48Chris Lattner  if (isInput) {
156af50315a29600188a6ff8b935beca6f1b59edf48Chris Lattner    if (Inst->getParent() != CurBB) {
157af50315a29600188a6ff8b935beca6f1b59edf48Chris Lattner      // If it is an input defined in a different block, then it remains an
158af50315a29600188a6ff8b935beca6f1b59edf48Chris Lattner      // input.
159af50315a29600188a6ff8b935beca6f1b59edf48Chris Lattner      return Inst;
160af50315a29600188a6ff8b935beca6f1b59edf48Chris Lattner    }
161e09e98c2de28a7dbbc4d3712c174596443a7a3f1Chris Lattner
162e09e98c2de28a7dbbc4d3712c174596443a7a3f1Chris Lattner    // If 'Inst' is defined in this block and is an input that needs to be phi
163e09e98c2de28a7dbbc4d3712c174596443a7a3f1Chris Lattner    // translated, we need to incorporate the value into the expression or fail.
164e09e98c2de28a7dbbc4d3712c174596443a7a3f1Chris Lattner
1656200e53f55536f812153ad910e6a69139592301bChris Lattner    // In either case, the instruction itself isn't an input any longer.
1666200e53f55536f812153ad910e6a69139592301bChris Lattner    InstInputs.erase(std::find(InstInputs.begin(), InstInputs.end(), Inst));
1677feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
1686fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    // If this is a PHI, go ahead and translate it.
1696fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    if (PHINode *PN = dyn_cast<PHINode>(Inst))
1706200e53f55536f812153ad910e6a69139592301bChris Lattner      return AddAsInput(PN->getIncomingValueForBlock(PredBB));
1717feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
1726fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    // If this is a non-phi value, and it is analyzable, we can incorporate it
1736fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    // into the expression by making all instruction operands be inputs.
1746fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    if (!CanPHITrans(Inst))
1756fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner      return 0;
1767feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
1776fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    // All instruction operands are now inputs (and of course, they may also be
1786fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    // defined in this block, so they may need to be phi translated themselves.
1796fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
1806fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner      if (Instruction *Op = dyn_cast<Instruction>(Inst->getOperand(i)))
1816fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner        InstInputs.push_back(Op);
1826fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  }
1836fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner
1846fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  // Ok, it must be an intermediate result (either because it started that way
1856fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  // or because we just incorporated it into the expression).  See if its
1866fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  // operands need to be phi translated, and if so, reconstruct it.
1877feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
188ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman  if (CastInst *Cast = dyn_cast<CastInst>(Inst)) {
189ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman    if (!Cast->isSafeToSpeculativelyExecute()) return 0;
190ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman    Value *PHIIn = PHITranslateSubExpr(Cast->getOperand(0), CurBB, PredBB, DT);
1916fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    if (PHIIn == 0) return 0;
192ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman    if (PHIIn == Cast->getOperand(0))
193ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman      return Cast;
1947feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
1956fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    // Find an available version of this cast.
1967feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
1976fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    // Constants are trivial to find.
1986fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    if (Constant *C = dyn_cast<Constant>(PHIIn))
199ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman      return AddAsInput(ConstantExpr::getCast(Cast->getOpcode(),
200ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman                                              C, Cast->getType()));
2017feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
202ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman    // Otherwise we have to see if a casted version of the incoming pointer
2036fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    // is available.  If so, we can use it, otherwise we have to fail.
2046fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    for (Value::use_iterator UI = PHIIn->use_begin(), E = PHIIn->use_end();
2056fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner         UI != E; ++UI) {
206ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman      if (CastInst *CastI = dyn_cast<CastInst>(*UI))
207ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman        if (CastI->getOpcode() == Cast->getOpcode() &&
208ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman            CastI->getType() == Cast->getType() &&
209ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman            (!DT || DT->dominates(CastI->getParent(), PredBB)))
210ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman          return CastI;
2116fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    }
2126fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    return 0;
2136fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  }
2147feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
2156fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  // Handle getelementptr with at least one PHI translatable operand.
2166fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
2176fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    SmallVector<Value*, 8> GEPOps;
2186fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    bool AnyChanged = false;
2196fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
2206d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar      Value *GEPOp = PHITranslateSubExpr(GEP->getOperand(i), CurBB, PredBB, DT);
2216fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner      if (GEPOp == 0) return 0;
2227feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
2236045417fcc21b1c0663120b9f24ec822f5d17cfeChris Lattner      AnyChanged |= GEPOp != GEP->getOperand(i);
2246fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner      GEPOps.push_back(GEPOp);
2259a8641201b2db8427be2a6531c043f384562c081Chris Lattner    }
2267feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
2276fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    if (!AnyChanged)
2286fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner      return GEP;
2297feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
2306fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    // Simplify the GEP to handle 'gep x, 0' -> x etc.
231b9b54ebfed02f0654897d37e8a4448d3f8087558Jay Foad    if (Value *V = SimplifyGEPInst(GEPOps, TD, DT)) {
2326200e53f55536f812153ad910e6a69139592301bChris Lattner      for (unsigned i = 0, e = GEPOps.size(); i != e; ++i)
2336200e53f55536f812153ad910e6a69139592301bChris Lattner        RemoveInstInputs(GEPOps[i], InstInputs);
2347feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
2356200e53f55536f812153ad910e6a69139592301bChris Lattner      return AddAsInput(V);
2366200e53f55536f812153ad910e6a69139592301bChris Lattner    }
2377feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
2386fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    // Scan to see if we have this GEP available.
2396fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    Value *APHIOp = GEPOps[0];
2406fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    for (Value::use_iterator UI = APHIOp->use_begin(), E = APHIOp->use_end();
2416fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner         UI != E; ++UI) {
2426fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner      if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI))
2436fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner        if (GEPI->getType() == GEP->getType() &&
2446fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner            GEPI->getNumOperands() == GEPOps.size() &&
2456d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar            GEPI->getParent()->getParent() == CurBB->getParent() &&
2466d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar            (!DT || DT->dominates(GEPI->getParent(), PredBB))) {
2476fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner          bool Mismatch = false;
2486fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner          for (unsigned i = 0, e = GEPOps.size(); i != e; ++i)
2496fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner            if (GEPI->getOperand(i) != GEPOps[i]) {
2506fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner              Mismatch = true;
2516fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner              break;
2526fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner            }
2536fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner          if (!Mismatch)
2546fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner            return GEPI;
2556fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner        }
2569a8641201b2db8427be2a6531c043f384562c081Chris Lattner    }
2576fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    return 0;
2586fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  }
2597feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
2606fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  // Handle add with a constant RHS.
2616fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  if (Inst->getOpcode() == Instruction::Add &&
2626fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner      isa<ConstantInt>(Inst->getOperand(1))) {
2636fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    // PHI translate the LHS.
2646fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    Constant *RHS = cast<ConstantInt>(Inst->getOperand(1));
2656fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    bool isNSW = cast<BinaryOperator>(Inst)->hasNoSignedWrap();
2666fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    bool isNUW = cast<BinaryOperator>(Inst)->hasNoUnsignedWrap();
2677feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
2686d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar    Value *LHS = PHITranslateSubExpr(Inst->getOperand(0), CurBB, PredBB, DT);
2696fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    if (LHS == 0) return 0;
2707feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
2716fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    // If the PHI translated LHS is an add of a constant, fold the immediates.
2726fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(LHS))
2736fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner      if (BOp->getOpcode() == Instruction::Add)
2746fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner        if (ConstantInt *CI = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
2756fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner          LHS = BOp->getOperand(0);
2766fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner          RHS = ConstantExpr::getAdd(RHS, CI);
2776fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner          isNSW = isNUW = false;
2787feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
2796200e53f55536f812153ad910e6a69139592301bChris Lattner          // If the old 'LHS' was an input, add the new 'LHS' as an input.
2806200e53f55536f812153ad910e6a69139592301bChris Lattner          if (std::count(InstInputs.begin(), InstInputs.end(), BOp)) {
2816200e53f55536f812153ad910e6a69139592301bChris Lattner            RemoveInstInputs(BOp, InstInputs);
2826200e53f55536f812153ad910e6a69139592301bChris Lattner            AddAsInput(LHS);
2836200e53f55536f812153ad910e6a69139592301bChris Lattner          }
2846fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner        }
2857feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
2866fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    // See if the add simplifies away.
287618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier    if (Value *Res = SimplifyAddInst(LHS, RHS, isNSW, isNUW, TD, TLI, DT)) {
2886200e53f55536f812153ad910e6a69139592301bChris Lattner      // If we simplified the operands, the LHS is no longer an input, but Res
2896200e53f55536f812153ad910e6a69139592301bChris Lattner      // is.
2906200e53f55536f812153ad910e6a69139592301bChris Lattner      RemoveInstInputs(LHS, InstInputs);
2916200e53f55536f812153ad910e6a69139592301bChris Lattner      return AddAsInput(Res);
2926200e53f55536f812153ad910e6a69139592301bChris Lattner    }
2934d3a16f81b2a0f0211b58f2c1e5a28e2bbd432c7Chris Lattner
2944d3a16f81b2a0f0211b58f2c1e5a28e2bbd432c7Chris Lattner    // If we didn't modify the add, just return it.
2954d3a16f81b2a0f0211b58f2c1e5a28e2bbd432c7Chris Lattner    if (LHS == Inst->getOperand(0) && RHS == Inst->getOperand(1))
2964d3a16f81b2a0f0211b58f2c1e5a28e2bbd432c7Chris Lattner      return Inst;
2977feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
2986fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    // Otherwise, see if we have this add available somewhere.
2996fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner    for (Value::use_iterator UI = LHS->use_begin(), E = LHS->use_end();
3006fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner         UI != E; ++UI) {
3016fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner      if (BinaryOperator *BO = dyn_cast<BinaryOperator>(*UI))
302eddc65aa0da35ee906e27cc7a13f44260c70007cChris Lattner        if (BO->getOpcode() == Instruction::Add &&
303eddc65aa0da35ee906e27cc7a13f44260c70007cChris Lattner            BO->getOperand(0) == LHS && BO->getOperand(1) == RHS &&
3046d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar            BO->getParent()->getParent() == CurBB->getParent() &&
3056d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar            (!DT || DT->dominates(BO->getParent(), PredBB)))
3066fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner          return BO;
3079a8641201b2db8427be2a6531c043f384562c081Chris Lattner    }
3087feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
3099a8641201b2db8427be2a6531c043f384562c081Chris Lattner    return 0;
3109a8641201b2db8427be2a6531c043f384562c081Chris Lattner  }
3117feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
3126fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  // Otherwise, we failed.
3136fcca1cc874c2b374b05399be92c5c1ea2086cc0Chris Lattner  return 0;
314210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner}
315210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner
3169a8641201b2db8427be2a6531c043f384562c081Chris Lattner
3179a8641201b2db8427be2a6531c043f384562c081Chris Lattner/// PHITranslateValue - PHI translate the current address up the CFG from
3186d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar/// CurBB to Pred, updating our state to reflect any needed changes.  If the
3196d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar/// dominator tree DT is non-null, the translated value must dominate
3206d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar/// PredBB.  This returns true on failure and sets Addr to null.
3216d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbarbool PHITransAddr::PHITranslateValue(BasicBlock *CurBB, BasicBlock *PredBB,
3226d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar                                     const DominatorTree *DT) {
3237dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  assert(Verify() && "Invalid PHITransAddr!");
3246d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar  Addr = PHITranslateSubExpr(Addr, CurBB, PredBB, DT);
3257dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner  assert(Verify() && "Invalid PHITransAddr!");
3269a8641201b2db8427be2a6531c043f384562c081Chris Lattner
3276d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar  if (DT) {
3286d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar    // Make sure the value is live in the predecessor.
3296d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar    if (Instruction *Inst = dyn_cast_or_null<Instruction>(Addr))
3306d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar      if (!DT->dominates(Inst->getParent(), PredBB))
3316d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar        Addr = 0;
3326d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar  }
3338c0c99016b4348bf9cc294a0f2dd60a219d4506cDaniel Dunbar
3346d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar  return Addr == 0;
3356d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar}
3368c0c99016b4348bf9cc294a0f2dd60a219d4506cDaniel Dunbar
3379a8641201b2db8427be2a6531c043f384562c081Chris Lattner/// PHITranslateWithInsertion - PHI translate this value into the specified
3389a8641201b2db8427be2a6531c043f384562c081Chris Lattner/// predecessor block, inserting a computation of the value if it is
3399a8641201b2db8427be2a6531c043f384562c081Chris Lattner/// unavailable.
3409a8641201b2db8427be2a6531c043f384562c081Chris Lattner///
3419a8641201b2db8427be2a6531c043f384562c081Chris Lattner/// All newly created instructions are added to the NewInsts list.  This
3429a8641201b2db8427be2a6531c043f384562c081Chris Lattner/// returns null on failure.
3439a8641201b2db8427be2a6531c043f384562c081Chris Lattner///
3449a8641201b2db8427be2a6531c043f384562c081Chris LattnerValue *PHITransAddr::
3459a8641201b2db8427be2a6531c043f384562c081Chris LattnerPHITranslateWithInsertion(BasicBlock *CurBB, BasicBlock *PredBB,
3469a8641201b2db8427be2a6531c043f384562c081Chris Lattner                          const DominatorTree &DT,
3479a8641201b2db8427be2a6531c043f384562c081Chris Lattner                          SmallVectorImpl<Instruction*> &NewInsts) {
3489a8641201b2db8427be2a6531c043f384562c081Chris Lattner  unsigned NISize = NewInsts.size();
3497feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
3509a8641201b2db8427be2a6531c043f384562c081Chris Lattner  // Attempt to PHI translate with insertion.
3519a8641201b2db8427be2a6531c043f384562c081Chris Lattner  Addr = InsertPHITranslatedSubExpr(Addr, CurBB, PredBB, DT, NewInsts);
3527feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
3539a8641201b2db8427be2a6531c043f384562c081Chris Lattner  // If successful, return the new value.
3549a8641201b2db8427be2a6531c043f384562c081Chris Lattner  if (Addr) return Addr;
3557feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
3569a8641201b2db8427be2a6531c043f384562c081Chris Lattner  // If not, destroy any intermediate instructions inserted.
3579a8641201b2db8427be2a6531c043f384562c081Chris Lattner  while (NewInsts.size() != NISize)
3589a8641201b2db8427be2a6531c043f384562c081Chris Lattner    NewInsts.pop_back_val()->eraseFromParent();
3599a8641201b2db8427be2a6531c043f384562c081Chris Lattner  return 0;
3609a8641201b2db8427be2a6531c043f384562c081Chris Lattner}
3619a8641201b2db8427be2a6531c043f384562c081Chris Lattner
3629a8641201b2db8427be2a6531c043f384562c081Chris Lattner
363210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner/// InsertPHITranslatedPointer - Insert a computation of the PHI translated
364210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner/// version of 'V' for the edge PredBB->CurBB into the end of the PredBB
365210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner/// block.  All newly created instructions are added to the NewInsts list.
366210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner/// This returns null on failure.
367210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner///
368210e45af3a579beeefb001c8f13c94e80407aad5Chris LattnerValue *PHITransAddr::
3699a8641201b2db8427be2a6531c043f384562c081Chris LattnerInsertPHITranslatedSubExpr(Value *InVal, BasicBlock *CurBB,
3709a8641201b2db8427be2a6531c043f384562c081Chris Lattner                           BasicBlock *PredBB, const DominatorTree &DT,
3719a8641201b2db8427be2a6531c043f384562c081Chris Lattner                           SmallVectorImpl<Instruction*> &NewInsts) {
372210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner  // See if we have a version of this value already available and dominating
3739a8641201b2db8427be2a6531c043f384562c081Chris Lattner  // PredBB.  If so, there is no need to insert a new instance of it.
3746d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar  PHITransAddr Tmp(InVal, TD);
3756d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar  if (!Tmp.PHITranslateValue(CurBB, PredBB, &DT))
3766d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar    return Tmp.getAddr();
377210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner
3789a8641201b2db8427be2a6531c043f384562c081Chris Lattner  // If we don't have an available version of this value, it must be an
3799a8641201b2db8427be2a6531c043f384562c081Chris Lattner  // instruction.
3809a8641201b2db8427be2a6531c043f384562c081Chris Lattner  Instruction *Inst = cast<Instruction>(InVal);
3817feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
382ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman  // Handle cast of PHI translatable value.
383ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman  if (CastInst *Cast = dyn_cast<CastInst>(Inst)) {
384ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman    if (!Cast->isSafeToSpeculativelyExecute()) return 0;
385ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman    Value *OpVal = InsertPHITranslatedSubExpr(Cast->getOperand(0),
3869a8641201b2db8427be2a6531c043f384562c081Chris Lattner                                              CurBB, PredBB, DT, NewInsts);
3879a8641201b2db8427be2a6531c043f384562c081Chris Lattner    if (OpVal == 0) return 0;
3887feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
389ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman    // Otherwise insert a cast at the end of PredBB.
390ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman    CastInst *New = CastInst::Create(Cast->getOpcode(),
391ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman                                     OpVal, InVal->getType(),
392ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman                                     InVal->getName()+".phi.trans.insert",
393ce562622118c40d5a24a07960c15cd4912db0cbfDan Gohman                                     PredBB->getTerminator());
3949a8641201b2db8427be2a6531c043f384562c081Chris Lattner    NewInsts.push_back(New);
3959a8641201b2db8427be2a6531c043f384562c081Chris Lattner    return New;
3969a8641201b2db8427be2a6531c043f384562c081Chris Lattner  }
3977feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
3989a8641201b2db8427be2a6531c043f384562c081Chris Lattner  // Handle getelementptr with at least one PHI operand.
3999a8641201b2db8427be2a6531c043f384562c081Chris Lattner  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
4009a8641201b2db8427be2a6531c043f384562c081Chris Lattner    SmallVector<Value*, 8> GEPOps;
4019a8641201b2db8427be2a6531c043f384562c081Chris Lattner    BasicBlock *CurBB = GEP->getParent();
4029a8641201b2db8427be2a6531c043f384562c081Chris Lattner    for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
4039a8641201b2db8427be2a6531c043f384562c081Chris Lattner      Value *OpVal = InsertPHITranslatedSubExpr(GEP->getOperand(i),
4049a8641201b2db8427be2a6531c043f384562c081Chris Lattner                                                CurBB, PredBB, DT, NewInsts);
4059a8641201b2db8427be2a6531c043f384562c081Chris Lattner      if (OpVal == 0) return 0;
4069a8641201b2db8427be2a6531c043f384562c081Chris Lattner      GEPOps.push_back(OpVal);
4079a8641201b2db8427be2a6531c043f384562c081Chris Lattner    }
4087feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
4097feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman    GetElementPtrInst *Result =
4102eb40f6d86ab44e7e642ea665afb28604008d367Frits van Bommel      GetElementPtrInst::Create(GEPOps[0], makeArrayRef(GEPOps).slice(1),
411a9203109f4ac95aa7e9624f2838e3d89623ec902Jay Foad                                InVal->getName()+".phi.trans.insert",
412a9203109f4ac95aa7e9624f2838e3d89623ec902Jay Foad                                PredBB->getTerminator());
4139a8641201b2db8427be2a6531c043f384562c081Chris Lattner    Result->setIsInBounds(GEP->isInBounds());
4149a8641201b2db8427be2a6531c043f384562c081Chris Lattner    NewInsts.push_back(Result);
4159a8641201b2db8427be2a6531c043f384562c081Chris Lattner    return Result;
4169a8641201b2db8427be2a6531c043f384562c081Chris Lattner  }
4177feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
4189a8641201b2db8427be2a6531c043f384562c081Chris Lattner#if 0
4199a8641201b2db8427be2a6531c043f384562c081Chris Lattner  // FIXME: This code works, but it is unclear that we actually want to insert
4209a8641201b2db8427be2a6531c043f384562c081Chris Lattner  // a big chain of computation in order to make a value available in a block.
4219a8641201b2db8427be2a6531c043f384562c081Chris Lattner  // This needs to be evaluated carefully to consider its cost trade offs.
4227feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
4239a8641201b2db8427be2a6531c043f384562c081Chris Lattner  // Handle add with a constant RHS.
4249a8641201b2db8427be2a6531c043f384562c081Chris Lattner  if (Inst->getOpcode() == Instruction::Add &&
4259a8641201b2db8427be2a6531c043f384562c081Chris Lattner      isa<ConstantInt>(Inst->getOperand(1))) {
4269a8641201b2db8427be2a6531c043f384562c081Chris Lattner    // PHI translate the LHS.
4279a8641201b2db8427be2a6531c043f384562c081Chris Lattner    Value *OpVal = InsertPHITranslatedSubExpr(Inst->getOperand(0),
4289a8641201b2db8427be2a6531c043f384562c081Chris Lattner                                              CurBB, PredBB, DT, NewInsts);
4299a8641201b2db8427be2a6531c043f384562c081Chris Lattner    if (OpVal == 0) return 0;
4307feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
4319a8641201b2db8427be2a6531c043f384562c081Chris Lattner    BinaryOperator *Res = BinaryOperator::CreateAdd(OpVal, Inst->getOperand(1),
4329a8641201b2db8427be2a6531c043f384562c081Chris Lattner                                           InVal->getName()+".phi.trans.insert",
4339a8641201b2db8427be2a6531c043f384562c081Chris Lattner                                                    PredBB->getTerminator());
4349a8641201b2db8427be2a6531c043f384562c081Chris Lattner    Res->setHasNoSignedWrap(cast<BinaryOperator>(Inst)->hasNoSignedWrap());
4359a8641201b2db8427be2a6531c043f384562c081Chris Lattner    Res->setHasNoUnsignedWrap(cast<BinaryOperator>(Inst)->hasNoUnsignedWrap());
4369a8641201b2db8427be2a6531c043f384562c081Chris Lattner    NewInsts.push_back(Res);
4379a8641201b2db8427be2a6531c043f384562c081Chris Lattner    return Res;
4389a8641201b2db8427be2a6531c043f384562c081Chris Lattner  }
4399a8641201b2db8427be2a6531c043f384562c081Chris Lattner#endif
4407feccd2af9160e28724eaa6701e49bf1c0db4920Dan Gohman
441210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner  return 0;
442210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner}
443