LCOV - code coverage report
Current view: top level - lib/Analysis - PHITransAddr.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 134 162 82.7 %
Date: 2017-09-14 15:23:50 Functions: 7 9 77.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- PHITransAddr.cpp - PHI Translation for Addresses -------------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file implements the PHITransAddr class.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "llvm/Analysis/PHITransAddr.h"
      15             : #include "llvm/Analysis/InstructionSimplify.h"
      16             : #include "llvm/Analysis/ValueTracking.h"
      17             : #include "llvm/IR/Constants.h"
      18             : #include "llvm/IR/Dominators.h"
      19             : #include "llvm/IR/Instructions.h"
      20             : #include "llvm/Support/Debug.h"
      21             : #include "llvm/Support/ErrorHandling.h"
      22             : #include "llvm/Support/raw_ostream.h"
      23             : using namespace llvm;
      24             : 
      25      118939 : static bool CanPHITrans(Instruction *Inst) {
      26      355142 :   if (isa<PHINode>(Inst) ||
      27      117264 :       isa<GetElementPtrInst>(Inst))
      28             :     return true;
      29             : 
      30       85714 :   if (isa<CastInst>(Inst) &&
      31        7552 :       isSafeToSpeculativelyExecute(Inst))
      32             :     return true;
      33             : 
      34       63549 :   if (Inst->getOpcode() == Instruction::Add &&
      35         982 :       isa<ConstantInt>(Inst->getOperand(1)))
      36             :     return true;
      37             : 
      38             :   //   cerr << "MEMDEP: Could not PHI translate: " << *Pointer;
      39             :   //   if (isa<BitCastInst>(PtrInst) || isa<GetElementPtrInst>(PtrInst))
      40             :   //     cerr << "OP:\t\t\t\t" << *PtrInst->getOperand(0);
      41             :   return false;
      42             : }
      43             : 
      44             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
      45             : LLVM_DUMP_METHOD void PHITransAddr::dump() const {
      46             :   if (!Addr) {
      47             :     dbgs() << "PHITransAddr: null\n";
      48             :     return;
      49             :   }
      50             :   dbgs() << "PHITransAddr: " << *Addr << "\n";
      51             :   for (unsigned i = 0, e = InstInputs.size(); i != e; ++i)
      52             :     dbgs() << "  Input #" << i << " is " << *InstInputs[i] << "\n";
      53             : }
      54             : #endif
      55             : 
      56             : 
      57           0 : static bool VerifySubExpr(Value *Expr,
      58             :                           SmallVectorImpl<Instruction*> &InstInputs) {
      59             :   // If this is a non-instruction value, there is nothing to do.
      60           0 :   Instruction *I = dyn_cast<Instruction>(Expr);
      61           0 :   if (!I) return true;
      62             : 
      63             :   // If it's an instruction, it is either in Tmp or its operands recursively
      64             :   // are.
      65           0 :   SmallVectorImpl<Instruction *>::iterator Entry = find(InstInputs, I);
      66           0 :   if (Entry != InstInputs.end()) {
      67           0 :     InstInputs.erase(Entry);
      68           0 :     return true;
      69             :   }
      70             : 
      71             :   // If it isn't in the InstInputs list it is a subexpr incorporated into the
      72             :   // address.  Sanity check that it is phi translatable.
      73           0 :   if (!CanPHITrans(I)) {
      74           0 :     errs() << "Instruction in PHITransAddr is not phi-translatable:\n";
      75           0 :     errs() << *I << '\n';
      76           0 :     llvm_unreachable("Either something is missing from InstInputs or "
      77             :                      "CanPHITrans is wrong.");
      78             :   }
      79             : 
      80             :   // Validate the operands of the instruction.
      81           0 :   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
      82           0 :     if (!VerifySubExpr(I->getOperand(i), InstInputs))
      83             :       return false;
      84             : 
      85             :   return true;
      86             : }
      87             : 
      88             : /// Verify - Check internal consistency of this data structure.  If the
      89             : /// structure is valid, it returns true.  If invalid, it prints errors and
      90             : /// returns false.
      91           0 : bool PHITransAddr::Verify() const {
      92           0 :   if (!Addr) return true;
      93             : 
      94           0 :   SmallVector<Instruction*, 8> Tmp(InstInputs.begin(), InstInputs.end());
      95             : 
      96           0 :   if (!VerifySubExpr(Addr, Tmp))
      97             :     return false;
      98             : 
      99           0 :   if (!Tmp.empty()) {
     100           0 :     errs() << "PHITransAddr contains extra instructions:\n";
     101           0 :     for (unsigned i = 0, e = InstInputs.size(); i != e; ++i)
     102           0 :       errs() << "  InstInput #" << i << " is " << *InstInputs[i] << "\n";
     103           0 :     llvm_unreachable("This is unexpected.");
     104             :   }
     105             : 
     106             :   // a-ok.
     107             :   return true;
     108             : }
     109             : 
     110             : 
     111             : /// IsPotentiallyPHITranslatable - If this needs PHI translation, return true
     112             : /// if we have some hope of doing it.  This should be used as a filter to
     113             : /// avoid calling PHITranslateValue in hopeless situations.
     114       36404 : bool PHITransAddr::IsPotentiallyPHITranslatable() const {
     115             :   // If the input value is not an instruction, or if it is not defined in CurBB,
     116             :   // then we don't need to phi translate it.
     117       72808 :   Instruction *Inst = dyn_cast<Instruction>(Addr);
     118       36404 :   return !Inst || CanPHITrans(Inst);
     119             : }
     120             : 
     121             : 
     122        1706 : static void RemoveInstInputs(Value *V,
     123             :                              SmallVectorImpl<Instruction*> &InstInputs) {
     124        1706 :   Instruction *I = dyn_cast<Instruction>(V);
     125        3412 :   if (!I) return;
     126             : 
     127             :   // If the instruction is in the InstInputs list, remove it.
     128         219 :   SmallVectorImpl<Instruction *>::iterator Entry = find(InstInputs, I);
     129         219 :   if (Entry != InstInputs.end()) {
     130         219 :     InstInputs.erase(Entry);
     131         219 :     return;
     132             :   }
     133             : 
     134             :   assert(!isa<PHINode>(I) && "Error, removing something that isn't an input");
     135             : 
     136             :   // Otherwise, it must have instruction inputs itself.  Zap them recursively.
     137           0 :   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
     138           0 :     if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i)))
     139           0 :       RemoveInstInputs(Op, InstInputs);
     140             :   }
     141             : }
     142             : 
     143      216507 : Value *PHITransAddr::PHITranslateSubExpr(Value *V, BasicBlock *CurBB,
     144             :                                          BasicBlock *PredBB,
     145             :                                          const DominatorTree *DT) {
     146             :   // If this is a non-instruction value, it can't require PHI translation.
     147      216507 :   Instruction *Inst = dyn_cast<Instruction>(V);
     148      216507 :   if (!Inst) return V;
     149             : 
     150             :   // Determine whether 'Inst' is an input to our PHI translatable expression.
     151      212158 :   bool isInput = is_contained(InstInputs, Inst);
     152             : 
     153             :   // Handle inputs instructions if needed.
     154      106079 :   if (isInput) {
     155      103020 :     if (Inst->getParent() != CurBB) {
     156             :       // If it is an input defined in a different block, then it remains an
     157             :       // input.
     158             :       return Inst;
     159             :     }
     160             : 
     161             :     // If 'Inst' is defined in this block and is an input that needs to be phi
     162             :     // translated, we need to incorporate the value into the expression or fail.
     163             : 
     164             :     // In either case, the instruction itself isn't an input any longer.
     165      182972 :     InstInputs.erase(find(InstInputs, Inst));
     166             : 
     167             :     // If this is a PHI, go ahead and translate it.
     168      100437 :     if (PHINode *PN = dyn_cast<PHINode>(Inst))
     169       17902 :       return AddAsInput(PN->getIncomingValueForBlock(PredBB));
     170             : 
     171             :     // If this is a non-phi value, and it is analyzable, we can incorporate it
     172             :     // into the expression by making all instruction operands be inputs.
     173       82535 :     if (!CanPHITrans(Inst))
     174             :       return nullptr;
     175             : 
     176             :     // All instruction operands are now inputs (and of course, they may also be
     177             :     // defined in this block, so they may need to be phi translated themselves.
     178      263215 :     for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
     179      479373 :       if (Instruction *Op = dyn_cast<Instruction>(Inst->getOperand(i)))
     180       49338 :         InstInputs.push_back(Op);
     181             :   }
     182             : 
     183             :   // Ok, it must be an intermediate result (either because it started that way
     184             :   // or because we just incorporated it into the expression).  See if its
     185             :   // operands need to be phi translated, and if so, reconstruct it.
     186             : 
     187       60282 :   if (CastInst *Cast = dyn_cast<CastInst>(Inst)) {
     188        5511 :     if (!isSafeToSpeculativelyExecute(Cast)) return nullptr;
     189       11022 :     Value *PHIIn = PHITranslateSubExpr(Cast->getOperand(0), CurBB, PredBB, DT);
     190        5511 :     if (!PHIIn) return nullptr;
     191        7026 :     if (PHIIn == Cast->getOperand(0))
     192             :       return Cast;
     193             : 
     194             :     // Find an available version of this cast.
     195             : 
     196             :     // Constants are trivial to find.
     197          27 :     if (Constant *C = dyn_cast<Constant>(PHIIn))
     198          54 :       return AddAsInput(ConstantExpr::getCast(Cast->getOpcode(),
     199          27 :                                               C, Cast->getType()));
     200             : 
     201             :     // Otherwise we have to see if a casted version of the incoming pointer
     202             :     // is available.  If so, we can use it, otherwise we have to fail.
     203        7114 :     for (User *U : PHIIn->users()) {
     204         205 :       if (CastInst *CastI = dyn_cast<CastInst>(U))
     205         596 :         if (CastI->getOpcode() == Cast->getOpcode() &&
     206         389 :             CastI->getType() == Cast->getType() &&
     207           0 :             (!DT || DT->dominates(CastI->getParent(), PredBB)))
     208             :           return CastI;
     209             :     }
     210             :     return nullptr;
     211             :   }
     212             : 
     213             :   // Handle getelementptr with at least one PHI translatable operand.
     214       97915 :   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
     215       97310 :     SmallVector<Value*, 8> GEPOps;
     216       48655 :     bool AnyChanged = false;
     217      220527 :     for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
     218      154845 :       Value *GEPOp = PHITranslateSubExpr(GEP->getOperand(i), CurBB, PredBB, DT);
     219      154845 :       if (!GEPOp) return nullptr;
     220             : 
     221      123217 :       AnyChanged |= GEPOp != GEP->getOperand(i);
     222      123217 :       GEPOps.push_back(GEPOp);
     223             :     }
     224             : 
     225       17027 :     if (!AnyChanged)
     226             :       return GEP;
     227             : 
     228             :     // Simplify the GEP to handle 'gep x, 0' -> x etc.
     229       15832 :     if (Value *V = SimplifyGEPInst(GEP->getSourceElementType(),
     230        3958 :                                    GEPOps, {DL, TLI, DT, AC})) {
     231        2340 :       for (unsigned i = 0, e = GEPOps.size(); i != e; ++i)
     232        2772 :         RemoveInstInputs(GEPOps[i], InstInputs);
     233             : 
     234         477 :       return AddAsInput(V);
     235             :     }
     236             : 
     237             :     // Scan to see if we have this GEP available.
     238        3481 :     Value *APHIOp = GEPOps[0];
     239       68402 :     for (User *U : APHIOp->users()) {
     240       24076 :       if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U))
     241       36287 :         if (GEPI->getType() == GEP->getType() &&
     242       35829 :             GEPI->getNumOperands() == GEPOps.size() &&
     243       40673 :             GEPI->getParent()->getParent() == CurBB->getParent() &&
     244         272 :             (!DT || DT->dominates(GEPI->getParent(), PredBB))) {
     245       20124 :           if (std::equal(GEPOps.begin(), GEPOps.end(), GEPI->op_begin()))
     246             :             return GEPI;
     247             :         }
     248             :     }
     249             :     return nullptr;
     250             :   }
     251             : 
     252             :   // Handle add with a constant RHS.
     253        1815 :   if (Inst->getOpcode() == Instruction::Add &&
     254        1210 :       isa<ConstantInt>(Inst->getOperand(1))) {
     255             :     // PHI translate the LHS.
     256        1815 :     Constant *RHS = cast<ConstantInt>(Inst->getOperand(1));
     257         605 :     bool isNSW = cast<BinaryOperator>(Inst)->hasNoSignedWrap();
     258        1210 :     bool isNUW = cast<BinaryOperator>(Inst)->hasNoUnsignedWrap();
     259             : 
     260        1210 :     Value *LHS = PHITranslateSubExpr(Inst->getOperand(0), CurBB, PredBB, DT);
     261         605 :     if (!LHS) return nullptr;
     262             : 
     263             :     // If the PHI translated LHS is an add of a constant, fold the immediates.
     264         386 :     if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(LHS))
     265         316 :       if (BOp->getOpcode() == Instruction::Add)
     266         468 :         if (ConstantInt *CI = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
     267         312 :           LHS = BOp->getOperand(0);
     268         156 :           RHS = ConstantExpr::getAdd(RHS, CI);
     269         156 :           isNSW = isNUW = false;
     270             : 
     271             :           // If the old 'LHS' was an input, add the new 'LHS' as an input.
     272         312 :           if (is_contained(InstInputs, BOp)) {
     273         156 :             RemoveInstInputs(BOp, InstInputs);
     274             :             AddAsInput(LHS);
     275             :           }
     276             :         }
     277             : 
     278             :     // See if the add simplifies away.
     279         772 :     if (Value *Res = SimplifyAddInst(LHS, RHS, isNSW, isNUW, {DL, TLI, DT, AC})) {
     280             :       // If we simplified the operands, the LHS is no longer an input, but Res
     281             :       // is.
     282         164 :       RemoveInstInputs(LHS, InstInputs);
     283         164 :       return AddAsInput(Res);
     284             :     }
     285             : 
     286             :     // If we didn't modify the add, just return it.
     287         639 :     if (LHS == Inst->getOperand(0) && RHS == Inst->getOperand(1))
     288             :       return Inst;
     289             : 
     290             :     // Otherwise, see if we have this add available somewhere.
     291        1018 :     for (User *U : LHS->users()) {
     292         239 :       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U))
     293         478 :         if (BO->getOpcode() == Instruction::Add &&
     294         482 :             BO->getOperand(0) == LHS && BO->getOperand(1) == RHS &&
     295         247 :             BO->getParent()->getParent() == CurBB->getParent() &&
     296           0 :             (!DT || DT->dominates(BO->getParent(), PredBB)))
     297             :           return BO;
     298             :     }
     299             : 
     300             :     return nullptr;
     301             :   }
     302             : 
     303             :   // Otherwise, we failed.
     304             :   return nullptr;
     305             : }
     306             : 
     307             : 
     308             : /// PHITranslateValue - PHI translate the current address up the CFG from
     309             : /// CurBB to Pred, updating our state to reflect any needed changes.  If
     310             : /// 'MustDominate' is true, the translated value must dominate
     311             : /// PredBB.  This returns true on failure and sets Addr to null.
     312      283878 : bool PHITransAddr::PHITranslateValue(BasicBlock *CurBB, BasicBlock *PredBB,
     313             :                                      const DominatorTree *DT,
     314             :                                      bool MustDominate) {
     315             :   assert(DT || !MustDominate);
     316             :   assert(Verify() && "Invalid PHITransAddr!");
     317      283878 :   if (DT && DT->isReachableFromEntry(PredBB))
     318       55546 :     Addr =
     319      111092 :         PHITranslateSubExpr(Addr, CurBB, PredBB, MustDominate ? DT : nullptr);
     320             :   else
     321      228332 :     Addr = nullptr;
     322             :   assert(Verify() && "Invalid PHITransAddr!");
     323             : 
     324      283878 :   if (MustDominate)
     325             :     // Make sure the value is live in the predecessor.
     326        3302 :     if (Instruction *Inst = dyn_cast_or_null<Instruction>(Addr))
     327         691 :       if (!DT->dominates(Inst->getParent(), PredBB))
     328          75 :         Addr = nullptr;
     329             : 
     330      283878 :   return Addr == nullptr;
     331             : }
     332             : 
     333             : /// PHITranslateWithInsertion - PHI translate this value into the specified
     334             : /// predecessor block, inserting a computation of the value if it is
     335             : /// unavailable.
     336             : ///
     337             : /// All newly created instructions are added to the NewInsts list.  This
     338             : /// returns null on failure.
     339             : ///
     340        2210 : Value *PHITransAddr::
     341             : PHITranslateWithInsertion(BasicBlock *CurBB, BasicBlock *PredBB,
     342             :                           const DominatorTree &DT,
     343             :                           SmallVectorImpl<Instruction*> &NewInsts) {
     344        4420 :   unsigned NISize = NewInsts.size();
     345             : 
     346             :   // Attempt to PHI translate with insertion.
     347        2210 :   Addr = InsertPHITranslatedSubExpr(Addr, CurBB, PredBB, DT, NewInsts);
     348             : 
     349             :   // If successful, return the new value.
     350        2210 :   if (Addr) return Addr;
     351             : 
     352             :   // If not, destroy any intermediate instructions inserted.
     353          22 :   while (NewInsts.size() != NISize)
     354           0 :     NewInsts.pop_back_val()->eraseFromParent();
     355             :   return nullptr;
     356             : }
     357             : 
     358             : 
     359             : /// InsertPHITranslatedPointer - Insert a computation of the PHI translated
     360             : /// version of 'V' for the edge PredBB->CurBB into the end of the PredBB
     361             : /// block.  All newly created instructions are added to the NewInsts list.
     362             : /// This returns null on failure.
     363             : ///
     364        2611 : Value *PHITransAddr::
     365             : InsertPHITranslatedSubExpr(Value *InVal, BasicBlock *CurBB,
     366             :                            BasicBlock *PredBB, const DominatorTree &DT,
     367             :                            SmallVectorImpl<Instruction*> &NewInsts) {
     368             :   // See if we have a version of this value already available and dominating
     369             :   // PredBB.  If so, there is no need to insert a new instance of it.
     370        7833 :   PHITransAddr Tmp(InVal, DL, AC);
     371        2611 :   if (!Tmp.PHITranslateValue(CurBB, PredBB, &DT, /*MustDominate=*/true))
     372        2484 :     return Tmp.getAddr();
     373             : 
     374             :   // We don't need to PHI translate values which aren't instructions.
     375         126 :   auto *Inst = dyn_cast<Instruction>(InVal);
     376             :   if (!Inst)
     377             :     return nullptr;
     378             : 
     379             :   // Handle cast of PHI translatable value.
     380         126 :   if (CastInst *Cast = dyn_cast<CastInst>(Inst)) {
     381          12 :     if (!isSafeToSpeculativelyExecute(Cast)) return nullptr;
     382          24 :     Value *OpVal = InsertPHITranslatedSubExpr(Cast->getOperand(0),
     383          12 :                                               CurBB, PredBB, DT, NewInsts);
     384          12 :     if (!OpVal) return nullptr;
     385             : 
     386             :     // Otherwise insert a cast at the end of PredBB.
     387          22 :     CastInst *New = CastInst::Create(Cast->getOpcode(), OpVal, InVal->getType(),
     388          33 :                                      InVal->getName() + ".phi.trans.insert",
     389          22 :                                      PredBB->getTerminator());
     390          44 :     New->setDebugLoc(Inst->getDebugLoc());
     391          11 :     NewInsts.push_back(New);
     392          11 :     return New;
     393             :   }
     394             : 
     395             :   // Handle getelementptr with at least one PHI operand.
     396         104 :   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
     397         208 :     SmallVector<Value*, 8> GEPOps;
     398         104 :     BasicBlock *CurBB = GEP->getParent();
     399         587 :     for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
     400         389 :       Value *OpVal = InsertPHITranslatedSubExpr(GEP->getOperand(i),
     401         389 :                                                 CurBB, PredBB, DT, NewInsts);
     402         389 :       if (!OpVal) return nullptr;
     403         379 :       GEPOps.push_back(OpVal);
     404             :     }
     405             : 
     406         188 :     GetElementPtrInst *Result = GetElementPtrInst::Create(
     407         188 :         GEP->getSourceElementType(), GEPOps[0], makeArrayRef(GEPOps).slice(1),
     408         282 :         InVal->getName() + ".phi.trans.insert", PredBB->getTerminator());
     409         376 :     Result->setDebugLoc(Inst->getDebugLoc());
     410          94 :     Result->setIsInBounds(GEP->isInBounds());
     411          94 :     NewInsts.push_back(Result);
     412          94 :     return Result;
     413             :   }
     414             : 
     415             : #if 0
     416             :   // FIXME: This code works, but it is unclear that we actually want to insert
     417             :   // a big chain of computation in order to make a value available in a block.
     418             :   // This needs to be evaluated carefully to consider its cost trade offs.
     419             : 
     420             :   // Handle add with a constant RHS.
     421             :   if (Inst->getOpcode() == Instruction::Add &&
     422             :       isa<ConstantInt>(Inst->getOperand(1))) {
     423             :     // PHI translate the LHS.
     424             :     Value *OpVal = InsertPHITranslatedSubExpr(Inst->getOperand(0),
     425             :                                               CurBB, PredBB, DT, NewInsts);
     426             :     if (OpVal == 0) return 0;
     427             : 
     428             :     BinaryOperator *Res = BinaryOperator::CreateAdd(OpVal, Inst->getOperand(1),
     429             :                                            InVal->getName()+".phi.trans.insert",
     430             :                                                     PredBB->getTerminator());
     431             :     Res->setHasNoSignedWrap(cast<BinaryOperator>(Inst)->hasNoSignedWrap());
     432             :     Res->setHasNoUnsignedWrap(cast<BinaryOperator>(Inst)->hasNoUnsignedWrap());
     433             :     NewInsts.push_back(Res);
     434             :     return Res;
     435             :   }
     436             : #endif
     437             : 
     438             :   return nullptr;
     439             : }

Generated by: LCOV version 1.13