[GVN] Add phi-translate for scalarpre as a temporary solution

[wmi]

Summary

Now phi-translate only exists in loadpre. scalarpre doesn't have phi-translate support, so it will miss some simple pre opportunities. Like the following testcase, current scalarpre cannot recognize the last "a * b" is fully redundent because a and b used by the last "a * b" expr are both defined by phis.

long a[100], b[100];
long g1, g2, g3;

attribute((pure))
long goo();

void foo(long a, long b, long c, long d) {

g1 = a * b;
if (__builtin_expect(g2 > 3, 0)) {
  a = c;
  b = d;
  g2 = a * b;
}
g3 = a * b;      // fully redundant.

}

The patch adds support for phi-translate in scalarpre. This is only a temporary solution before the newpre based on newgvn is available.

[• dberlin]

A few things.

1. There is, strangely, a doPhiTranslation function that Value has, you can use that :)

2. Newgvn gets this example case without PRE with my latest patch

It understand the equivalence between op of phis and phi of ops, and so comes up with:

define void @test1(i64 %a, i64 %b, i64 %c, i64 %d) {
entry:
  %mul = mul nsw i64 %b, %a
  store i64 %mul, i64* @g1, align 8
  %t0 = load i64, i64* @g2, align 8
  %cmp = icmp sgt i64 %t0, 3
  br i1 %cmp, label %if.then, label %if.end

if.then:                                          ; preds = %entry
  %mul2 = mul nsw i64 %d, %c
  store i64 %mul2, i64* @g2, align 8
  br label %if.end

if.end:                                           ; preds = %if.then, %entry
  %0 = phi i64 [ %mul2, %if.then ], [ %mul, %entry ]
  store i64 %0, i64* @g3, align 8
  ret void
}

3. I suspect you will have issues with backedges with this approach

I'm pretty sure it will fail in some cases to fixpoint (but maybe gvn is not strong enough to make that happen)

At the very least, you don't want this to transform:

a = phi(0, a + 1)
use a
to
a = phi(0, a + 1)
b = phi(1, a + 2)

etc
It will peel loops ivs if you let it.
In gcc, we specifically check for this case.

[• dberlin]

This also needs compile time and performance measurements.

[wmi]

Daniel, thanks for the comments.

There is, strangely, a doPhiTranslation function that Value has, you can use that :)

Yes, I can use it to simplify phiTranslateImpl a little.

Newgvn gets this example case without PRE with my latest patch. It understand the equivalence between op of phis and phi of ops

Good job for newgvn :-).

I suspect you will have issues with backedges with this approach. I'm pretty sure it will fail in some cases to fixpoint (but maybe gvn is not strong enough to make that happen)
At the very least, you don't want this to transform:

There is code in performScalarPRE checking whether the predecessor is the same as current bb and giving up if it is true. I tried small testcase and it seemed fine. I will pay attention to it when exercise it with more tests.

This also needs compile time and performance measurements.

Sure. I will do it.

[• dberlin]

I suspect you will have issues with backedges with this approach. I'm pretty sure it will fail in some cases to fixpoint (but maybe gvn is not strong enough to make that happen)
At the very least, you don't want this to transform:

There is code in performScalarPRE checking whether the predecessor is the same as current bb and giving up if it is true. I tried small testcase and it seemed fine. I will pay attention to it when exercise it with more tests.

This code will only work for the trivialest of cases :)

GVN computes the RPO ordering.
The easiest way to detect backedges is to densemap that.
An edge x->y is a backedge if RPO[x] >= RPO[y]

(This is because in a postorder traversal, you are guaranteed it will find the edges that lead to a block, before that block, since it will process all children to completion first
So in a PO, PO[x] <= PO[y], since it will process all such children of y before processing y.
In RPO, it's just reversed)

[davide]

Marking request changes so it gets off of my queue while you're taking performance/compile time numbers

[wmi]

Forgot to update the patch.

prevent phi-translate from going through back edge.

[wmi]

I change the DenseMap numberingExpression (mapping from value numbering to GVN::Expression) to std::vector. Although there is still some minor increase but better than before.

400.perlbench 0.81%
401.bzip2 -0.11%
403.gcc -0.42%
429.mcf 1.58%
433.milc -0.33%
445.gobmk 0.85%
456.hmmer 0.07%
458.sjeng -0.42%
462.libquantum -0.75%
464.h264ref -1.24%
470.lbm -0.65%
482.sphinx3 0.44%
998.specrand 0.00%
999.specrand -1.74%
444.namd 0.28%
447.dealII 1.56%
450.soplex 0.96%
453.povray -0.02%
471.omnetpp 0.02%
473.astar 0.18%
483.xalancbmk 0.85%

[davide]

In D32252#750282, @wmi wrote:

I change the DenseMap numberingExpression (mapping from value numbering to GVN::Expression) to std::vector. Although there is still some minor increase but better than before.

400.perlbench 0.81%
401.bzip2 -0.11%
403.gcc -0.42%
429.mcf 1.58%
433.milc -0.33%
445.gobmk 0.85%
456.hmmer 0.07%
458.sjeng -0.42%
462.libquantum -0.75%
464.h264ref -1.24%
470.lbm -0.65%
482.sphinx3 0.44%
998.specrand 0.00%
999.specrand -1.74%
444.namd 0.28%
447.dealII 1.56%
450.soplex 0.96%
453.povray -0.02%
471.omnetpp 0.02%
473.astar 0.18%
483.xalancbmk 0.85%

The compile time numbers don't look particularly bad. Thanks.
Can you try on large testcases/LTO (maybe of clang itself) to confirm that scales in a sane way?

[davide]

I'm a little surprised that bootstrapping without LTO takes more time than bootstrapping with LTO, but assuming numbers are sane, the compile time impact is not terrible.

[• dberlin]

Pretty good at this point.
I don't understand why you changed the CHECK-NEXT lines to CHECK lines though.
Can you explain?

lib/Transforms/Scalar/GVN.cpp

239 ↗

(On Diff #98361)

Just initialize it to false in the constructor

[wmi]

Initialize commutative in Expression's constructor.
Fix a bug related with commutative: need to swap cmp predicate at the same time when we swap the operands.

[• dberlin]

At this point, i think this is reasonable. we know what the cost is, it seems reasonable given the benefits, and we know it's not long term.
the code seems clean etc.
i"m going to accept this, but i'd just wait a day to see if anyone else has comments before committing.

Thank you for working through this with folks :)

[davide]

Fine by me. Thanks!

[wmi]

No more comments seen so prepare to commit the patch. Thanks for the review!

[alekseyshl]

This bot failure seem to be related to this change: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux/builds/2086/steps/build%20compiler-rt%20android%2Farm/logs/stdio (based on phiTranslate in the stack)

llvm/trunk/include/llvm/Transforms/Scalar/GVN.h

public:
   struct Expression;
 
   /// This class holds the mapping between values and value numbers.  It is used
   /// as an efficient mechanism to determine the expression-wise equivalence of
   /// two values.
   class ValueTable {
     DenseMap<Value *, uint32_t> valueNumbering;
     DenseMap<Expression, uint32_t> expressionNumbering;
+
+    // Expressions is the vector of Expression. ExprIdx is the mapping from
+    // value number to the index of Expression in Expressions. We use it
+    // instead of a DenseMap because filling such mapping is faster than
+    // filling a DenseMap and the compile time is a little better.
+    uint32_t nextExprNumber;
+    std::vector<Expression> Expressions;
+    std::vector<uint32_t> ExprIdx;
+    // Value number to PHINode mapping. Used for phi-translate in scalarpre.
+    DenseMap<uint32_t, PHINode *> NumberingPhi;
+    // Cache for phi-translate in scalarpre.
+    typedef DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>
+        PhiTranslateMap;
+    PhiTranslateMap PhiTranslateTable;
+    // Map the block to reversed postorder traversal number. It is used to
+    // find back edge easily.
+    DenseMap<const BasicBlock *, uint32_t> BlockRPONumber;
+
     AliasAnalysis *AA;
     MemoryDependenceResults *MD;
     DominatorTree *DT;
 
     uint32_t nextValueNumber;
 
     Expression createExpr(Instruction *I);
     Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
                              Value *LHS, Value *RHS);
     Expression createExtractvalueExpr(ExtractValueInst *EI);
     uint32_t lookupOrAddCall(CallInst *C);
+    uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
+                              uint32_t Num, GVN &Gvn);
+    std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
+    bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVN &Gvn);
 
   public:
     ValueTable();
     ValueTable(const ValueTable &Arg);
     ValueTable(ValueTable &&Arg);
     ~ValueTable();
 
     uint32_t lookupOrAdd(Value *V);
-    uint32_t lookup(Value *V) const;
+    uint32_t lookup(Value *V, bool Verify = true) const;
     uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
                             Value *LHS, Value *RHS);
+    uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
+                          uint32_t Num, GVN &Gvn);
+    void assignBlockRPONumber(Function &F);
     bool exists(Value *V) const;
     void add(Value *V, uint32_t num);
     void clear();
     void erase(Value *v);
     void setAliasAnalysis(AliasAnalysis *A) { AA = A; }
     AliasAnalysis *getAliasAnalysis() const { return AA; }
     void setMemDep(MemoryDependenceResults *M) { MD = M; }
     void setDomTree(DominatorTree *D) { DT = D; }

llvm/trunk/lib/Transforms/Scalar/GVN.cpp

 // Maximum allowed recursion depth.
 static cl::opt<uint32_t>
 MaxRecurseDepth("max-recurse-depth", cl::Hidden, cl::init(1000), cl::ZeroOrMore,
                 cl::desc("Max recurse depth (default = 1000)"));
 
 struct llvm::GVN::Expression {
   uint32_t opcode;
   Type *type;
+  bool commutative;
   SmallVector<uint32_t, 4> varargs;
 
-  Expression(uint32_t o = ~2U) : opcode(o) {}
+  Expression(uint32_t o = ~2U) : opcode(o), commutative(false) {}
 
   bool operator==(const Expression &other) const {
     if (opcode != other.opcode)
       return false;
     if (opcode == ~0U || opcode == ~1U)
       return true;
     if (type != other.type)
       return false;
GVN::Expression GVN::ValueTable::createExpr(Instruction *I) {
   if (I->isCommutative()) {
     // Ensure that commutative instructions that only differ by a permutation
     // of their operands get the same value number by sorting the operand value
     // numbers.  Since all commutative instructions have two operands it is more
     // efficient to sort by hand rather than using, say, std::sort.
     assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!");
     if (e.varargs[0] > e.varargs[1])
       std::swap(e.varargs[0], e.varargs[1]);
+    e.commutative = true;
   }
 
   if (CmpInst *C = dyn_cast<CmpInst>(I)) {
     // Sort the operand value numbers so x<y and y>x get the same value number.
     CmpInst::Predicate Predicate = C->getPredicate();
     if (e.varargs[0] > e.varargs[1]) {
       std::swap(e.varargs[0], e.varargs[1]);
       Predicate = CmpInst::getSwappedPredicate(Predicate);
     }
     e.opcode = (C->getOpcode() << 8) | Predicate;
+    e.commutative = true;
   } else if (InsertValueInst *E = dyn_cast<InsertValueInst>(I)) {
     for (InsertValueInst::idx_iterator II = E->idx_begin(), IE = E->idx_end();
          II != IE; ++II)
       e.varargs.push_back(*II);
   }
 
   return e;
 }
GVN::Expression GVN::ValueTable::createCmpExpr(unsigned Opcode,
   e.varargs.push_back(lookupOrAdd(RHS));
 
   // Sort the operand value numbers so x<y and y>x get the same value number.
   if (e.varargs[0] > e.varargs[1]) {
     std::swap(e.varargs[0], e.varargs[1]);
     Predicate = CmpInst::getSwappedPredicate(Predicate);
   }
   e.opcode = (Opcode << 8) | Predicate;
+  e.commutative = true;
   return e;
 }
 
 GVN::Expression GVN::ValueTable::createExtractvalueExpr(ExtractValueInst *EI) {
   assert(EI && "Not an ExtractValueInst?");
   Expression e;
   e.type = EI->getType();
   e.opcode = 0;

 GVN::ValueTable::ValueTable() : nextValueNumber(1) {}
 GVN::ValueTable::ValueTable(const ValueTable &) = default;
 GVN::ValueTable::ValueTable(ValueTable &&) = default;
 GVN::ValueTable::~ValueTable() = default;
 
 /// add - Insert a value into the table with a specified value number.
 void GVN::ValueTable::add(Value *V, uint32_t num) {
   valueNumbering.insert(std::make_pair(V, num));
+  if (PHINode *PN = dyn_cast<PHINode>(V))
+    NumberingPhi[num] = PN;
 }
 
 uint32_t GVN::ValueTable::lookupOrAddCall(CallInst *C) {
   if (AA->doesNotAccessMemory(C)) {
     Expression exp = createExpr(C);
-    uint32_t &e = expressionNumbering[exp];
-    if (!e) e = nextValueNumber++;
+    uint32_t e = assignExpNewValueNum(exp).first;
     valueNumbering[C] = e;
     return e;
   } else if (AA->onlyReadsMemory(C)) {
     Expression exp = createExpr(C);
-    uint32_t &e = expressionNumbering[exp];
-    if (!e) {
-      e = nextValueNumber++;
-      valueNumbering[C] = e;
-      return e;
+    auto ValNum = assignExpNewValueNum(exp);
+    if (ValNum.second) {
+      valueNumbering[C] = ValNum.first;
+      return ValNum.first;
     }
     if (!MD) {
-      e = nextValueNumber++;
+      uint32_t e = assignExpNewValueNum(exp).first;
       valueNumbering[C] = e;
       return e;
     }
 
     MemDepResult local_dep = MD->getDependency(C);
 
     if (!local_dep.isDef() && !local_dep.isNonLocal()) {
       valueNumbering[C] =  nextValueNumber;
switch (I->getOpcode()) {
     case Instruction::ShuffleVector:
     case Instruction::InsertValue:
     case Instruction::GetElementPtr:
       exp = createExpr(I);
       break;
     case Instruction::ExtractValue:
       exp = createExtractvalueExpr(cast<ExtractValueInst>(I));
       break;
+    case Instruction::PHI:
+      valueNumbering[V] = nextValueNumber;
+      NumberingPhi[nextValueNumber] = cast<PHINode>(V);
+      return nextValueNumber++;
     default:
       valueNumbering[V] = nextValueNumber;
       return nextValueNumber++;
   }
 
-  uint32_t& e = expressionNumbering[exp];
-  if (!e) e = nextValueNumber++;
+  uint32_t e = assignExpNewValueNum(exp).first;
   valueNumbering[V] = e;
   return e;
 }
 
 /// Returns the value number of the specified value. Fails if
 /// the value has not yet been numbered.
-uint32_t GVN::ValueTable::lookup(Value *V) const {
+uint32_t GVN::ValueTable::lookup(Value *V, bool Verify) const {
   DenseMap<Value*, uint32_t>::const_iterator VI = valueNumbering.find(V);
+  if (Verify) {
     assert(VI != valueNumbering.end() && "Value not numbered?");
     return VI->second;
   }
+  return (VI != valueNumbering.end()) ? VI->second : 0;
+}
 
 /// Returns the value number of the given comparison,
 /// assigning it a new number if it did not have one before.  Useful when
 /// we deduced the result of a comparison, but don't immediately have an
 /// instruction realizing that comparison to hand.
 uint32_t GVN::ValueTable::lookupOrAddCmp(unsigned Opcode,
                                          CmpInst::Predicate Predicate,
                                          Value *LHS, Value *RHS) {
   Expression exp = createCmpExpr(Opcode, Predicate, LHS, RHS);
-  uint32_t& e = expressionNumbering[exp];
-  if (!e) e = nextValueNumber++;
-  return e;
+  return assignExpNewValueNum(exp).first;
 }
 
 /// Remove all entries from the ValueTable.
 void GVN::ValueTable::clear() {
   valueNumbering.clear();
   expressionNumbering.clear();
+  NumberingPhi.clear();
+  PhiTranslateTable.clear();
+  BlockRPONumber.clear();
   nextValueNumber = 1;
+  Expressions.clear();
+  ExprIdx.clear();
+  nextExprNumber = 0;
 }
 
 /// Remove a value from the value numbering.
 void GVN::ValueTable::erase(Value *V) {
+  uint32_t Num = valueNumbering.lookup(V);
   valueNumbering.erase(V);
+  // If V is PHINode, V <--> value number is an one-to-one mapping.
+  if (isa<PHINode>(V))
+    NumberingPhi.erase(Num);
 }
 
 /// verifyRemoved - Verify that the value is removed from all internal data
 /// structures.
 void GVN::ValueTable::verifyRemoved(const Value *V) const {
   for (DenseMap<Value*, uint32_t>::const_iterator
          I = valueNumbering.begin(), E = valueNumbering.end(); I != E; ++I) {
     assert(I->first != V && "Inst still occurs in value numbering map!");
if (AnalyzeLoadAvailability(L, Dep, L->getPointerOperand(), AV)) {
     if (MD && AvailableValue->getType()->getScalarType()->isPointerTy())
       MD->invalidateCachedPointerInfo(AvailableValue);
     return true;
   }
 
   return false;
 }
 
+/// Return a pair the first field showing the value number of \p Exp and the
+/// second field showing whether it is a value number newly created.
+std::pair<uint32_t, bool>
+GVN::ValueTable::assignExpNewValueNum(Expression &Exp) {
+  uint32_t &e = expressionNumbering[Exp];
+  bool CreateNewValNum = !e;
+  if (CreateNewValNum) {
+    Expressions.push_back(Exp);
+    if (ExprIdx.size() < nextValueNumber + 1)
+      ExprIdx.resize(nextValueNumber * 2);
+    e = nextValueNumber;
+    ExprIdx[nextValueNumber++] = nextExprNumber++;
+  }
+  return {e, CreateNewValNum};
+}
+
+void GVN::ValueTable::assignBlockRPONumber(Function &F) {
+  uint32_t NextBlockNumber = 1;
+  ReversePostOrderTraversal<Function *> RPOT(&F);
+  for (BasicBlock *BB : RPOT)
+    BlockRPONumber[BB] = NextBlockNumber++;
+}
+
+/// Return whether all the values related with the same \p num are
+/// defined in \p BB.
+bool GVN::ValueTable::areAllValsInBB(uint32_t Num, const BasicBlock *BB,
+                                     GVN &Gvn) {
+  LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
+  while (Vals && Vals->BB == BB)
+    Vals = Vals->Next;
+  return !Vals;
+}
+
+/// Wrap phiTranslateImpl to provide caching functionality.
+uint32_t GVN::ValueTable::phiTranslate(const BasicBlock *Pred,
+                                       const BasicBlock *PhiBlock, uint32_t Num,
+                                       GVN &Gvn) {
+  auto FindRes = PhiTranslateTable.find({Num, Pred});
+  if (FindRes != PhiTranslateTable.end())
+    return FindRes->second;
+  uint32_t NewNum = phiTranslateImpl(Pred, PhiBlock, Num, Gvn);
+  PhiTranslateTable.insert({{Num, Pred}, NewNum});
+  return NewNum;
+}
+
+/// Translate value number \p Num using phis, so that it has the values of
+/// the phis in BB.
+uint32_t GVN::ValueTable::phiTranslateImpl(const BasicBlock *Pred,
+                                           const BasicBlock *PhiBlock,
+                                           uint32_t Num, GVN &Gvn) {
+  if (PHINode *PN = NumberingPhi[Num]) {
+    if (BlockRPONumber[Pred] >= BlockRPONumber[PhiBlock])
+      return Num;
+    for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
+      if (PN->getParent() == PhiBlock && PN->getIncomingBlock(i) == Pred)
+        if (uint32_t TransVal = lookup(PN->getIncomingValue(i), false))
+          return TransVal;
+    }
+    return Num;
+  }
+
+  // If there is any value related with Num is defined in a BB other than
+  // PhiBlock, it cannot depend on a phi in PhiBlock without going through
+  // a backedge. We can do an early exit in that case to save compile time.
+  if (!areAllValsInBB(Num, PhiBlock, Gvn))
+    return Num;
+
+  if (ExprIdx[Num] == 0 || Num >= ExprIdx.size())
+    return Num;
+  Expression Exp = Expressions[ExprIdx[Num]];
+
+  for (unsigned i = 0; i < Exp.varargs.size(); i++)
+    Exp.varargs[i] = phiTranslate(Pred, PhiBlock, Exp.varargs[i], Gvn);
+
+  if (Exp.commutative) {
+    assert(Exp.varargs.size() == 2 && "Unsupported commutative expression!");
+    if (Exp.varargs[0] > Exp.varargs[1]) {
+      std::swap(Exp.varargs[0], Exp.varargs[1]);
+      uint32_t Opcode = Exp.opcode >> 8;
+      if (Opcode == Instruction::ICmp || Opcode == Instruction::FCmp)
+        Exp.opcode = (Opcode << 8) |
+                     CmpInst::getSwappedPredicate(
+                         static_cast<CmpInst::Predicate>(Exp.opcode & 255));
+    }
+  }
+
+  if (uint32_t NewNum = expressionNumbering[Exp])
+    return NewNum;
+  return Num;
+}
+
 // In order to find a leader for a given value number at a
 // specific basic block, we first obtain the list of all Values for that number,
 // and then scan the list to find one whose block dominates the block in
 // question.  This is fast because dominator tree queries consist of only
 // a few comparisons of DFS numbers.
 Value *GVN::findLeader(const BasicBlock *BB, uint32_t num) {
   LeaderTableEntry Vals = LeaderTable[num];
   if (!Vals.Val) return nullptr;
while (ShouldContinue) {
     Changed |= ShouldContinue;
     ++Iteration;
   }
 
   if (EnablePRE) {
     // Fabricate val-num for dead-code in order to suppress assertion in
     // performPRE().
     assignValNumForDeadCode();
+    VN.assignBlockRPONumber(F);
     bool PREChanged = true;
     while (PREChanged) {
       PREChanged = performPRE(F);
       Changed |= PREChanged;
     }
   }
 
   // FIXME: Should perform GVN again after PRE does something.  PRE can move
for (unsigned i = 0, e = Instr->getNumOperands(); i != e; ++i) {
     // This could be a newly inserted instruction, in which case, we won't
     // find a value number, and should give up before we hurt ourselves.
     // FIXME: Rewrite the infrastructure to let it easier to value number
     // and process newly inserted instructions.
     if (!VN.exists(Op)) {
       success = false;
       break;
     }
-    if (Value *V = findLeader(Pred, VN.lookup(Op))) {
+    uint32_t TValNo =
+        VN.phiTranslate(Pred, Instr->getParent(), VN.lookup(Op), *this);
+    if (Value *V = findLeader(Pred, TValNo)) {
       Instr->setOperand(i, V);
     } else {
       success = false;
       break;
     }
   }
 
   // Fail out if we encounter an operand that is not available in
   // the PRE predecessor.  This is typically because of loads which
   // are not value numbered precisely.
   if (!success)
     return false;
 
   Instr->insertBefore(Pred->getTerminator());
   Instr->setName(Instr->getName() + ".pre");
   Instr->setDebugLoc(Instr->getDebugLoc());
-  VN.add(Instr, ValNo);
+
+  unsigned Num = VN.lookupOrAdd(Instr);
+  VN.add(Instr, Num);
 
   // Update the availability map to include the new instruction.
-  addToLeaderTable(ValNo, Instr, Pred);
+  addToLeaderTable(Num, Instr, Pred);
   return true;
 }
 
 bool GVN::performScalarPRE(Instruction *CurInst) {
   if (isa<AllocaInst>(CurInst) || isa<TerminatorInst>(CurInst) ||
       isa<PHINode>(CurInst) || CurInst->getType()->isVoidTy() ||
       CurInst->mayReadFromMemory() || CurInst->mayHaveSideEffects() ||
       isa<DbgInfoIntrinsic>(CurInst))
for (BasicBlock *P : predecessors(CurrentBlock)) {
     if (P == CurrentBlock) {
       NumWithout = 2;
       break;
     } else if (!DT->isReachableFromEntry(P)) {
       NumWithout = 2;
       break;
     }
 
-    Value *predV = findLeader(P, ValNo);
+    uint32_t TValNo = VN.phiTranslate(P, CurrentBlock, ValNo, *this);
+    Value *predV = findLeader(P, TValNo);
     if (!predV) {
       predMap.push_back(std::make_pair(static_cast<Value *>(nullptr), P));
       PREPred = P;
       ++NumWithout;
     } else if (predV == CurInst) {
       /* CurInst dominates this predecessor. */
       NumWithout = 2;
       break;

llvm/trunk/test/Transforms/GVN/PRE/phi-translate-2.ll

+; RUN: opt < %s -gvn -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@a = common global [100 x i64] zeroinitializer, align 16
+@b = common global [100 x i64] zeroinitializer, align 16
+@g1 = common global i64 0, align 8
+@g2 = common global i64 0, align 8
+@g3 = common global i64 0, align 8
+declare i64 @goo(...) local_unnamed_addr #1
+
+define void @test1(i64 %a, i64 %b, i64 %c, i64 %d) {
+entry:
+  %mul = mul nsw i64 %b, %a
+  store i64 %mul, i64* @g1, align 8
+  %t0 = load i64, i64* @g2, align 8
+  %cmp = icmp sgt i64 %t0, 3
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %mul2 = mul nsw i64 %d, %c
+  store i64 %mul2, i64* @g2, align 8
+  br label %if.end
+
+; Check phi-translate works and mul is removed.
+; CHECK-LABEL: @test1(
+; CHECK: if.end:
+; CHECK: %[[MULPHI:.*]] = phi i64 [ {{.*}}, %if.then ], [ %mul, %entry ]
+; CHECK-NOT: = mul
+; CHECK: store i64 %[[MULPHI]], i64* @g3, align 8
+if.end:                                           ; preds = %if.then, %entry
+  %b.addr.0 = phi i64 [ %d, %if.then ], [ %b, %entry ]
+  %a.addr.0 = phi i64 [ %c, %if.then ], [ %a, %entry ]
+  %mul3 = mul nsw i64 %a.addr.0, %b.addr.0
+  store i64 %mul3, i64* @g3, align 8
+  ret void
+}
+
+define void @test2(i64 %i) {
+entry:
+  %arrayidx = getelementptr inbounds [100 x i64], [100 x i64]* @a, i64 0, i64 %i
+  %t0 = load i64, i64* %arrayidx, align 8
+  %arrayidx1 = getelementptr inbounds [100 x i64], [100 x i64]* @b, i64 0, i64 %i
+  %t1 = load i64, i64* %arrayidx1, align 8
+  %mul = mul nsw i64 %t1, %t0
+  store i64 %mul, i64* @g1, align 8
+  %cmp = icmp sgt i64 %mul, 3
+  br i1 %cmp, label %if.then, label %if.end
+
+; Check phi-translate works for the phi generated by loadpre. A new mul will be
+; inserted in if.then block.
+; CHECK-LABEL: @test2(
+; CHECK: if.then:
+; CHECK: %[[MUL_THEN:.*]] = mul
+; CHECK: br label %if.end
+if.then:                                          ; preds = %entry
+  %call = tail call i64 (...) @goo() #2
+  store i64 %call, i64* @g2, align 8
+  br label %if.end
+
+; CHECK: if.end:
+; CHECK: %[[MULPHI:.*]] = phi i64 [ %[[MUL_THEN]], %if.then ], [ %mul, %entry ]
+; CHECK-NOT: = mul
+; CHECK: store i64 %[[MULPHI]], i64* @g3, align 8
+if.end:                                           ; preds = %if.then, %entry
+  %i.addr.0 = phi i64 [ 3, %if.then ], [ %i, %entry ]
+  %arrayidx3 = getelementptr inbounds [100 x i64], [100 x i64]* @a, i64 0, i64 %i.addr.0
+  %t2 = load i64, i64* %arrayidx3, align 8
+  %arrayidx4 = getelementptr inbounds [100 x i64], [100 x i64]* @b, i64 0, i64 %i.addr.0
+  %t3 = load i64, i64* %arrayidx4, align 8
+  %mul5 = mul nsw i64 %t3, %t2
+  store i64 %mul5, i64* @g3, align 8
+  ret void
+}
+
+; Check phi-translate doesn't go through backedge, which may lead to incorrect
+; pre transformation.
+; CHECK: for.end:
+; CHECK-NOT: %{{.*pre-phi}} = phi
+; CHECK: ret void
+define void @test3(i64 %N, i64* nocapture readonly %a) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %i.0 = phi i64 [ 0, %entry ], [ %add, %for.body ]
+  %add = add nuw nsw i64 %i.0, 1
+  %arrayidx = getelementptr inbounds i64, i64* %a, i64 %add
+  %tmp0 = load i64, i64* %arrayidx, align 8
+  %cmp = icmp slt i64 %i.0, %N
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %call = tail call i64 (...) @goo() #2
+  %add1 = sub nsw i64 0, %call
+  %tobool = icmp eq i64 %tmp0, %add1
+  br i1 %tobool, label %for.cond, label %for.end
+
+for.end:                                          ; preds = %for.body, %for.cond
+  %i.0.lcssa = phi i64 [ %i.0, %for.body ], [ %i.0, %for.cond ]
+  %arrayidx2 = getelementptr inbounds i64, i64* %a, i64 %i.0.lcssa
+  %tmp1 = load i64, i64* %arrayidx2, align 8
+  store i64 %tmp1, i64* @g1, align 8
+  ret void
+}
+

llvm/trunk/test/Transforms/GVN/PRE/pre-gep-load.ll

 sw.bb2:                                           ; preds = %if.end, %entry
   %idxprom3 = sext i32 %i to i64
   %arrayidx4 = getelementptr inbounds double*, double** %p, i64 0
   %2 = load double*, double** %arrayidx4, align 8
   %arrayidx5 = getelementptr inbounds double, double* %2, i64 %idxprom3
   %3 = load double, double* %arrayidx5, align 8
 ; CHECK: sw.bb2:
 ; CHECK-NOT: sext
-; CHECK-NEXT: phi double [
+; CHECK: phi double [
 ; CHECK-NOT: load
   %sub6 = fsub double 3.000000e+00, %3
   br label %return
 
 sw.default:                                       ; preds = %entry
   br label %return
 
 return:                                           ; preds = %sw.default, %sw.bb2, %if.then

llvm/trunk/test/Transforms/GVN/PRE/pre-load.ll

block3:
   br label %block4
 
 block4:
   %P2 = phi i32* [%p, %block3], [%q, %block2]
   %P3 = getelementptr i32, i32* %P2, i32 1
   %PRE = load i32, i32* %P3
   ret i32 %PRE
 ; CHECK: block4:
-; CHECK-NEXT: phi i32 [
+; CHECK: phi i32 [
 ; CHECK-NOT: load
 ; CHECK: ret i32
 }
 
 ;; Here the loaded address is available, but the computation is in 'block3'
 ;; which does not dominate 'block2'.
 define i32 @test4(i32* %p, i32* %q, i32** %Hack, i1 %C) {
 ; CHECK-LABEL: @test4(
block3:
   br label %block4
 
 block4:
   %P2 = phi i32* [%p, %block3], [%q, %block2]
   %P3 = getelementptr i32, i32* %P2, i32 1
   %PRE = load i32, i32* %P3
   ret i32 %PRE
 ; CHECK: block4:
-; CHECK-NEXT: phi i32 [
+; CHECK: phi i32 [
 ; CHECK-NOT: load
 ; CHECK: ret i32
 }
 
 ;void test5(int N, double *G) {
 ;  int j;
 ;  for (j = 0; j < N - 1; j++)
 ;    G[j] = G[j] + G[j+1];
block3:
   br label %block4
 
 block4:
   %P2 = phi i32* [%p, %block3], [%q, %block2]
   %P3 = getelementptr i32, i32* %P2, i32 1
   %PRE = load i32, i32* %P3
   ret i32 %PRE
 ; CHECK: block4:
-; CHECK-NEXT: phi i32 [
+; CHECK: phi i32 [
 ; CHECK-NOT: load
 ; CHECK: ret i32
 }
 
 ;void test9(int N, double* G) {
 ;  long j;
 ;  for (j = 1; j < N - 1; j++)
 ;      G[j+1] = G[j] + G[j+1];