PredicateInfo: Support switch statements

[• dberlin]

Summary

Depends on D29606 and D29682

Makes us pass GVN's edge.ll (we also will pass a few other testcases
they just need cleaning up).

Thoughts on the Predicate* hiearchy of classes especially welcome :)
(it's not clear to me how best to organize it, and currently, the getBlock* seems ... uglier than maybe wasting a field somewhere or something).

[• dberlin]

lib/Transforms/Scalar/NewGVN.cpp

862 ↗

(On Diff #87755)

sigh, clang format, i'll fix

876 ↗

(On Diff #87755)

ditto

880 ↗

(On Diff #87755)

ditto

[• dberlin]

• Update new tests

[• dberlin]

lib/Transforms/Scalar/NewGVN.cpp

845 ↗

(On Diff #88091)

See comment below about branch having two parents.
The switch code is the only real new code in this function,

1061 ↗

(On Diff #88091)

Just a friendly note: This branch has two parents (the critical edge patch and the initial newgvn patch).
So this diff shows a lot more than is actually here.
In particular, this function is not really being added here.

[davide]

Once the basic predicate support goes in, can you please rebase this patch so I can review it more easily? Thanks!

[• dberlin]

Yup, as soon as those two are committed i'll rebase and ping you.

[• dberlin]

Rebase on top of master and clean up.

[davide]

lib/Transforms/Scalar/NewGVN.cpp

1152 ↗

(On Diff #89056)

Spurious newline

lib/Transforms/Utils/PredicateInfo.cpp

56–59 ↗

(On Diff #89056)

assert(isa<>) + return static_cast<> ?

65–67 ↗

(On Diff #89056)

Also here and in the other places.

442–450 ↗

(On Diff #89056)

range for?

[• dberlin]

• Update for review comments

Note: This adds two pair conversion function for BasicBlockEdge in
dominators to make life easier. We can't just use basicblockedge
ourselves, because we need non-const basic blocks in a few places.

[davide]

LGTM. Thanks.

llvm/trunk/include/llvm/Transforms/Utils/PredicateInfo.h

 class DominatorTree;
 class Function;
 class Instruction;
 class MemoryAccess;
 class LLVMContext;
 class raw_ostream;
 class OrderedBasicBlock;
 
-enum PredicateType { PT_Branch, PT_Assume };
+enum PredicateType { PT_Branch, PT_Assume, PT_Switch };
 
 // Base class for all predicate information we provide.
 // All of our predicate information has at least a comparison.
 class PredicateBase : public ilist_node<PredicateBase> {
 public:
   PredicateType Type;
   // The original operand before we renamed it.
   // This can be use by passes, when destroying predicateinfo, to know
   // whether they can just drop the intrinsic, or have to merge metadata.
   Value *OriginalOp;
-  Value *Condition;
   PredicateBase(const PredicateBase &) = delete;
   PredicateBase &operator=(const PredicateBase &) = delete;
   PredicateBase() = delete;
   virtual ~PredicateBase() = default;
 
 protected:
-  PredicateBase(PredicateType PT, Value *Op, Value *Condition)
-      : Type(PT), OriginalOp(Op), Condition(Condition) {}
+  PredicateBase(PredicateType PT, Value *Op) : Type(PT), OriginalOp(Op) {}
+};
+
+class PredicateWithCondition : public PredicateBase {
+public:
+  Value *Condition;
+  static inline bool classof(const PredicateBase *PB) {
+    return PB->Type == PT_Assume || PB->Type == PT_Branch || PB->Type == PT_Switch;
+  }
+
+protected:
+  PredicateWithCondition(PredicateType PT, Value *Op, Value *Condition)
+      : PredicateBase(PT, Op), Condition(Condition) {}
 };
 
 // Provides predicate information for assumes.  Since assumes are always true,
 // we simply provide the assume instruction, so you can tell your relative
 // position to it.
-class PredicateAssume : public PredicateBase {
+class PredicateAssume : public PredicateWithCondition {
 public:
   IntrinsicInst *AssumeInst;
   PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition)
-      : PredicateBase(PT_Assume, Op, Condition), AssumeInst(AssumeInst) {}
+      : PredicateWithCondition(PT_Assume, Op, Condition),
+        AssumeInst(AssumeInst) {}
   PredicateAssume() = delete;
   static inline bool classof(const PredicateBase *PB) {
     return PB->Type == PT_Assume;
   }
 };
 
+// Mixin class for edge predicates.  The FROM block is the block where the
+// predicate originates, and the TO block is the block where the predicate is
+// valid.
+class PredicateWithEdge : public PredicateWithCondition {
+public:
+  BasicBlock *From;
+  BasicBlock *To;
+  PredicateWithEdge() = delete;
+  static inline bool classof(const PredicateBase *PB) {
+    return PB->Type == PT_Branch || PB->Type == PT_Switch;
+  }
+
+protected:
+  PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From,
+                    BasicBlock *To, Value *Cond)
+      : PredicateWithCondition(PType, Op, Cond), From(From), To(To) {}
+};
+
 // Provides predicate information for branches.
-class PredicateBranch : public PredicateBase {
+class PredicateBranch : public PredicateWithEdge {
 public:
-  // This is the block that is conditional upon the condition.
-  BasicBlock *BranchBB;
-  // This is one of the true/false successors of BranchBB.
-  BasicBlock *SplitBB;
   // If true, SplitBB is the true successor, otherwise it's the false successor.
   bool TrueEdge;
   PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB,
                   Value *Condition, bool TakenEdge)
-      : PredicateBase(PT_Branch, Op, Condition), BranchBB(BranchBB),
-        SplitBB(SplitBB), TrueEdge(TakenEdge) {}
+      : PredicateWithEdge(PT_Branch, Op, BranchBB, SplitBB, Condition),
+        TrueEdge(TakenEdge) {}
   PredicateBranch() = delete;
   static inline bool classof(const PredicateBase *PB) {
     return PB->Type == PT_Branch;
   }
 };
 
+class PredicateSwitch : public PredicateWithEdge {
+public:
+  Value *CaseValue;
+  // This is the switch instruction.
+  SwitchInst *Switch;
+  PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB,
+                  Value *CaseValue, SwitchInst *SI)
+      : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB,
+                          SI->getCondition()),
+        CaseValue(CaseValue), Switch(SI) {}
+  PredicateSwitch() = delete;
+  static inline bool classof(const PredicateBase *PB) {
+    return PB->Type == PT_Switch;
+  }
+};
+
 // This name is used in a few places, so kick it into their own namespace
 namespace PredicateInfoClasses {
 struct ValueDFS;
 }
 
 /// \brief Encapsulates PredicateInfo, including all data associated with memory
 /// accesses.
 class PredicateInfo {
protected:
   // Used by PredicateInfo annotater, dumpers, and wrapper pass.
   friend class PredicateInfoAnnotatedWriter;
   friend class PredicateInfoPrinterLegacyPass;
 
 private:
   void buildPredicateInfo();
   void processAssume(IntrinsicInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
   void processBranch(BranchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
+  void processSwitch(SwitchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
   void renameUses(SmallPtrSetImpl<Value *> &);
   using ValueDFS = PredicateInfoClasses::ValueDFS;
   typedef SmallVectorImpl<ValueDFS> ValueDFSStack;
   void convertUsesToDFSOrdered(Value *, SmallVectorImpl<ValueDFS> &);
   Value *materializeStack(unsigned int &, ValueDFSStack &, Value *);
   bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const;
   void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &);
   ValueInfo &getOrCreateValueInfo(Value *);

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

 
 const Expression *
 NewGVN::performSymbolicPredicateInfoEvaluation(Instruction *I) {
   auto *PI = PredInfo->getPredicateInfoFor(I);
   if (!PI)
     return nullptr;
 
   DEBUG(dbgs() << "Found predicate info from instruction !\n");
-  auto *CopyOf = I->getOperand(0);
-  auto *Cond = dyn_cast<Instruction>(PI->Condition);
-  if (!Cond)
+
+  auto *PWC = dyn_cast<PredicateWithCondition>(PI);
+  if (!PWC)
     return nullptr;
 
+  auto *CopyOf = I->getOperand(0);
+  auto *Cond = PWC->Condition;
+
   // If this a copy of the condition, it must be either true or false depending
   // on the predicate info type and edge
   if (CopyOf == Cond) {
-    addPredicateUsers(PI, I);
+    // We should not need to add predicate users because the predicate info is
+    // already a use of this operand.
     if (isa<PredicateAssume>(PI))
       return createConstantExpression(ConstantInt::getTrue(Cond->getType()));
     if (auto *PBranch = dyn_cast<PredicateBranch>(PI)) {
       if (PBranch->TrueEdge)
         return createConstantExpression(ConstantInt::getTrue(Cond->getType()));
       return createConstantExpression(ConstantInt::getFalse(Cond->getType()));
     }
+    if (auto *PSwitch = dyn_cast<PredicateSwitch>(PI))
+      return createConstantExpression(cast<Constant>(PSwitch->CaseValue));
   }
-  // Not a copy of the condition, so see what the predicates tell us about this
-  // value.
+
   // Not a copy of the condition, so see what the predicates tell us about this
   // value.  First, though, we check to make sure the value is actually a copy
   // of one of the condition operands. It's possible, in certain cases, for it
   // to be a copy of a predicateinfo copy. In particular, if two branch
   // operations use the same condition, and one branch dominates the other, we
   // will end up with a copy of a copy.  This is currently a small deficiency in
-  // predicateinfo.   What will end up happening here is that we will value
+  // predicateinfo.  What will end up happening here is that we will value
   // number both copies the same anyway.
-  if (CopyOf != Cond->getOperand(0) && CopyOf != Cond->getOperand(1)) {
+
+  // Everything below relies on the condition being a comparison.
+  auto *Cmp = dyn_cast<CmpInst>(Cond);
+  if (!Cmp)
+    return nullptr;
+
+  if (CopyOf != Cmp->getOperand(0) && CopyOf != Cmp->getOperand(1)) {
     DEBUG(dbgs() << "Copy is not of any condition operands!");
     return nullptr;
   }
-  Value *FirstOp = lookupOperandLeader(Cond->getOperand(0));
-  Value *SecondOp = lookupOperandLeader(Cond->getOperand(1));
+  Value *FirstOp = lookupOperandLeader(Cmp->getOperand(0));
+  Value *SecondOp = lookupOperandLeader(Cmp->getOperand(1));
   bool SwappedOps = false;
   // Sort the ops
   if (shouldSwapOperands(FirstOp, SecondOp)) {
     std::swap(FirstOp, SecondOp);
     SwappedOps = true;
   }
-
-  // Everything below relies on the condition being a comparison.
-  auto *Cmp = dyn_cast<CmpInst>(Cond);
   CmpInst::Predicate Predicate =
       SwappedOps ? Cmp->getSwappedPredicate() : Cmp->getPredicate();
 
   if (isa<PredicateAssume>(PI)) {
     // If the comparison is true when the operands are equal, then we know the
     // operands are equal, because assumes must always be true.
     if (CmpInst::isTrueWhenEqual(Predicate)) {
       addPredicateUsers(PI, I);
const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) {
   auto OurPredicate = CI->getPredicate();
   if (shouldSwapOperands(Op1, Op0)) {
     std::swap(Op0, Op1);
     OurPredicate = CI->getSwappedPredicate();
   }
 
   // Avoid processing the same info twice
   const PredicateBase *LastPredInfo = nullptr;
-
   // See if we know something about the comparison itself, like it is the target
   // of an assume.
   auto *CmpPI = PredInfo->getPredicateInfoFor(I);
   if (dyn_cast_or_null<PredicateAssume>(CmpPI))
     return createConstantExpression(ConstantInt::getTrue(CI->getType()));
 
   if (Op0 == Op1) {
     // This condition does not depend on predicates, no need to add users
const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) {
   // See if our operands have predicate info, so that we may be able to derive
   // something from a previous comparison.
   for (const auto &Op : CI->operands()) {
     auto *PI = PredInfo->getPredicateInfoFor(Op);
     if (const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) {
       if (PI == LastPredInfo)
         continue;
       LastPredInfo = PI;
+
       // TODO: Along the false edge, we may know more things too, like icmp of
       // same operands is false.
       // TODO: We only handle actual comparison conditions below, not and/or.
       auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition);
       if (!BranchCond)
         continue;
       auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0));
       auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1));

llvm/trunk/lib/Transforms/Utils/PredicateInfo.cpp

INITIALIZE_PASS_BEGIN(PredicateInfoPrinterLegacyPass, "print-predicateinfo",
                       "PredicateInfo Printer", false, false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_END(PredicateInfoPrinterLegacyPass, "print-predicateinfo",
                     "PredicateInfo Printer", false, false)
 static cl::opt<bool> VerifyPredicateInfo(
     "verify-predicateinfo", cl::init(false), cl::Hidden,
     cl::desc("Verify PredicateInfo in legacy printer pass."));
+namespace {
 DEBUG_COUNTER(RenameCounter, "predicateinfo-rename",
               "Controls which variables are renamed with predicateinfo")
+// Given a predicate info that is a type of branching terminator, get the
+// branching block.
+const BasicBlock *getBranchBlock(const PredicateBase *PB) {
+  assert(isa<PredicateWithEdge>(PB) &&
+         "Only branches and switches should have PHIOnly defs that "
+         "require branch blocks.");
+  return cast<PredicateWithEdge>(PB)->From;
+}
+
+// Given a predicate info that is a type of branching terminator, get the
+// branching terminator.
+static Instruction *getBranchTerminator(const PredicateBase *PB) {
+  assert(isa<PredicateWithEdge>(PB) &&
+         "Not a predicate info type we know how to get a terminator from.");
+  return cast<PredicateWithEdge>(PB)->From->getTerminator();
+}
+
+// Given a predicate info that is a type of branching terminator, get the
+// edge this predicate info represents
+const std::pair<BasicBlock *, BasicBlock *>
+getBlockEdge(const PredicateBase *PB) {
+  assert(isa<PredicateWithEdge>(PB) &&
+         "Not a predicate info type we know how to get an edge from.");
+  const auto *PEdge = cast<PredicateWithEdge>(PB);
+  return std::make_pair(PEdge->From, PEdge->To);
+}
+}
 
 namespace llvm {
 namespace PredicateInfoClasses {
 enum LocalNum {
   // Operations that must appear first in the block.
   LN_First,
   // Operations that are somewhere in the middle of the block, and are sorted on
   // demand.
bool operator()(const ValueDFS &A, const ValueDFS &B) const {
 
     if (!SameBlock || A.LocalNum != LN_Middle || B.LocalNum != LN_Middle)
       return std::tie(A.DFSIn, A.DFSOut, A.LocalNum, A.Def, A.U) <
              std::tie(B.DFSIn, B.DFSOut, B.LocalNum, B.Def, B.U);
     return localComesBefore(A, B);
   }
 
   // For a phi use, or a non-materialized def, return the edge it represents.
-  const std::pair<const BasicBlock *, const BasicBlock *>
+  const std::pair<BasicBlock *, BasicBlock *>
   getBlockEdge(const ValueDFS &VD) const {
     if (!VD.Def && VD.U) {
       auto *PHI = cast<PHINode>(VD.U->getUser());
       return std::make_pair(PHI->getIncomingBlock(*VD.U), PHI->getParent());
     }
     // This is really a non-materialized def.
-    auto *PBranch = cast<PredicateBranch>(VD.PInfo);
-    return std::make_pair(PBranch->BranchBB, PBranch->SplitBB);
+    return ::getBlockEdge(VD.PInfo);
   }
 
   // For two phi related values, return the ordering.
   bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const {
     auto &ABlockEdge = getBlockEdge(A);
     auto &BBlockEdge = getBlockEdge(B);
     // Now sort by block edge and then defs before uses.
     return std::tie(ABlockEdge, A.Def, A.U) < std::tie(BBlockEdge, B.Def, B.U);
bool PredicateInfo::stackIsInScope(const ValueDFSStack &Stack,
   // the defs they must go with so that we can know it's time to pop the stack
   // when we hit the end of the phi uses for a given def.
   if (Stack.back().EdgeOnly) {
     if (!VDUse.U)
       return false;
     auto *PHI = dyn_cast<PHINode>(VDUse.U->getUser());
     if (!PHI)
       return false;
-    // The only EdgeOnly defs should be branch info.
-    auto *PBranch = dyn_cast<PredicateBranch>(Stack.back().PInfo);
-    assert(PBranch && "Only branches should have EdgeOnly defs");
-    // Check edge matches us.
+    // Check edge
     BasicBlock *EdgePred = PHI->getIncomingBlock(*VDUse.U);
-    if (EdgePred != PBranch->BranchBB)
+    if (EdgePred != getBranchBlock(Stack.back().PInfo))
       return false;
 
     // Use dominates, which knows how to handle edge dominance.
-    return DT.dominates(BasicBlockEdge(PBranch->BranchBB, PBranch->SplitBB),
-                        *VDUse.U);
+    return DT.dominates(getBlockEdge(Stack.back().PInfo), *VDUse.U);
   }
 
   return (VDUse.DFSIn >= Stack.back().DFSIn &&
           VDUse.DFSOut <= Stack.back().DFSOut);
 }
 
 void PredicateInfo::popStackUntilDFSScope(ValueDFSStack &Stack,
                                           const ValueDFS &VD) {
if (auto *Cmp = dyn_cast<CmpInst>(Cond)) {
       // as the comparison. It's either true or false on the true/false branch.
       InsertHelper(BinOp, false, false, BinOp);
     } else {
       llvm_unreachable("Unknown type of condition");
     }
     CmpOperands.clear();
   }
 }
+// Process a block terminating switch, and place relevant operations to be
+// renamed into OpsToRename.
+void PredicateInfo::processSwitch(SwitchInst *SI, BasicBlock *BranchBB,
+                                  SmallPtrSetImpl<Value *> &OpsToRename) {
+  Value *Op = SI->getCondition();
+  if ((!isa<Instruction>(Op) && !isa<Argument>(Op)) || Op->hasOneUse())
+    return;
+
+  // Remember how many outgoing edges there are to every successor.
+  SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
+  for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
+    BasicBlock *TargetBlock = SI->getSuccessor(i);
+    ++SwitchEdges[TargetBlock];
+  }
+
+  // Now propagate info for each case value
+  for (auto C : SI->cases()) {
+    BasicBlock *TargetBlock = C.getCaseSuccessor();
+    if (SwitchEdges.lookup(TargetBlock) == 1) {
+      PredicateSwitch *PS = new PredicateSwitch(
+          Op, SI->getParent(), TargetBlock, C.getCaseValue(), SI);
+      addInfoFor(OpsToRename, Op, PS);
+      if (!TargetBlock->getSinglePredecessor())
+        EdgeUsesOnly.insert({BranchBB, TargetBlock});
+    }
+  }
+}
 
 // Build predicate info for our function
 void PredicateInfo::buildPredicateInfo() {
   DT.updateDFSNumbers();
   // Collect operands to rename from all conditional branch terminators, as well
   // as assume statements.
   SmallPtrSet<Value *, 8> OpsToRename;
   for (auto DTN : depth_first(DT.getRootNode())) {
     BasicBlock *BranchBB = DTN->getBlock();
     if (auto *BI = dyn_cast<BranchInst>(BranchBB->getTerminator())) {
       if (!BI->isConditional())
         continue;
       processBranch(BI, BranchBB, OpsToRename);
+    } else if (auto *SI = dyn_cast<SwitchInst>(BranchBB->getTerminator())) {
+      processSwitch(SI, BranchBB, OpsToRename);
     }
   }
   for (auto &Assume : AC.assumptions()) {
     if (auto *II = dyn_cast_or_null<IntrinsicInst>(Assume))
       processAssume(II, II->getParent(), OpsToRename);
   }
   // Now rename all our operations.
   renameUses(OpsToRename);
 }
+
+// Given the renaming stack, make all the operands currently on the stack real
+// by inserting them into the IR.  Return the last operation's value.
 Value *PredicateInfo::materializeStack(unsigned int &Counter,
                                        ValueDFSStack &RenameStack,
                                        Value *OrigOp) {
   // Find the first thing we have to materialize
   auto RevIter = RenameStack.rbegin();
   for (; RevIter != RenameStack.rend(); ++RevIter)
     if (RevIter->Def)
       break;
 
   size_t Start = RevIter - RenameStack.rbegin();
   // The maximum number of things we should be trying to materialize at once
   // right now is 4, depending on if we had an assume, a branch, and both used
   // and of conditions.
   for (auto RenameIter = RenameStack.end() - Start;
        RenameIter != RenameStack.end(); ++RenameIter) {
     auto *Op =
         RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def;
     ValueDFS &Result = *RenameIter;
     auto *ValInfo = Result.PInfo;
-    // For branches, we can just place the operand in the branch block before
+    // For edge predicates, we can just place the operand in the block before
     // the terminator.  For assume, we have to place it right before the assume
     // to ensure we dominate all of our uses.  Always insert right before the
     // relevant instruction (terminator, assume), so that we insert in proper
     // order in the case of multiple predicateinfo in the same block.
-    if (isa<PredicateBranch>(ValInfo)) {
-      auto *PBranch = cast<PredicateBranch>(ValInfo);
-      IRBuilder<> B(PBranch->BranchBB->getTerminator());
+    if (isa<PredicateWithEdge>(ValInfo)) {
+      IRBuilder<> B(getBranchTerminator(ValInfo));
       Function *IF = Intrinsic::getDeclaration(
           F.getParent(), Intrinsic::ssa_copy, Op->getType());
       CallInst *PIC =
           B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++));
       PredicateMap.insert({PIC, ValInfo});
       Result.Def = PIC;
     } else {
       auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
for (auto &PossibleCopy : ValueInfo.Infos) {
         VD.LocalNum = LN_Middle;
         DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent());
         if (!DomNode)
           continue;
         VD.DFSIn = DomNode->getDFSNumIn();
         VD.DFSOut = DomNode->getDFSNumOut();
         VD.PInfo = PossibleCopy;
         OrderedUses.push_back(VD);
-      } else if (const auto *PBranch =
-                     dyn_cast<PredicateBranch>(PossibleCopy)) {
+      } else if (isa<PredicateWithEdge>(PossibleCopy)) {
         // If we can only do phi uses, we treat it like it's in the branch
         // block, and handle it specially. We know that it goes last, and only
         // dominate phi uses.
-        if (EdgeUsesOnly.count({PBranch->BranchBB, PBranch->SplitBB})) {
+        auto BlockEdge = getBlockEdge(PossibleCopy);
+        if (EdgeUsesOnly.count(BlockEdge)) {
           VD.LocalNum = LN_Last;
-          auto *DomNode = DT.getNode(PBranch->BranchBB);
+          auto *DomNode = DT.getNode(BlockEdge.first);
           if (DomNode) {
             VD.DFSIn = DomNode->getDFSNumIn();
             VD.DFSOut = DomNode->getDFSNumOut();
             VD.PInfo = PossibleCopy;
             VD.EdgeOnly = true;
             OrderedUses.push_back(VD);
           }
         } else {
           // Otherwise, we are in the split block (even though we perform
           // insertion in the branch block).
           // Insert a possible copy at the split block and before the branch.
           VD.LocalNum = LN_First;
-          auto *DomNode = DT.getNode(PBranch->SplitBB);
+          auto *DomNode = DT.getNode(BlockEdge.second);
           if (DomNode) {
             VD.DFSIn = DomNode->getDFSNumIn();
             VD.DFSOut = DomNode->getDFSNumOut();
             VD.PInfo = PossibleCopy;
             OrderedUses.push_back(VD);
           }
         }
       }
public:
 
   virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
                                         formatted_raw_ostream &OS) {}
 
   virtual void emitInstructionAnnot(const Instruction *I,
                                     formatted_raw_ostream &OS) {
     if (const auto *PI = PredInfo->getPredicateInfoFor(I)) {
       OS << "; Has predicate info\n";
-      if (const auto *PB = dyn_cast<PredicateBranch>(PI))
+      if (const auto *PB = dyn_cast<PredicateBranch>(PI)) {
         OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge
-           << " Comparison:" << *PB->Condition << " }\n";
-      else if (const auto *PA = dyn_cast<PredicateAssume>(PI))
+           << " Comparison:" << *PB->Condition << " Edge: [";
+        PB->From->printAsOperand(OS);
+        OS << ",";
+        PB->To->printAsOperand(OS);
+        OS << "] }\n";
+      } else if (const auto *PS = dyn_cast<PredicateSwitch>(PI)) {
+        OS << "; switch predicate info { CaseValue: " << *PS->CaseValue
+           << " Switch:" << *PS->Switch << " Edge: [";
+        PS->From->printAsOperand(OS);
+        OS << ",";
+        PS->To->printAsOperand(OS);
+        OS << "] }\n";
+      } else if (const auto *PA = dyn_cast<PredicateAssume>(PI)) {
         OS << "; assume predicate info {"
            << " Comparison:" << *PA->Condition << " }\n";
       }
     }
+  }
 };
 
 void PredicateInfo::print(raw_ostream &OS) const {
   PredicateInfoAnnotatedWriter Writer(this);
   F.print(OS, &Writer);
 }
 
 void PredicateInfo::dump() const {

llvm/trunk/test/Transforms/NewGVN/condprop.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -basicaa -newgvn -S | FileCheck %s
 
 
 declare void @foo(i1)
 declare void @bar(i32)
 
-; CHECK-LABEL: @test3(
 define void @test3(i32 %x, i32 %y) {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
+; CHECK-NEXT:    [[Z:%.*]] = and i1 [[XZ]], [[YZ]]
+; CHECK-NEXT:    br i1 [[Z]], label [[BOTH_ZERO:%.*]], label [[NOPE:%.*]]
+; CHECK:       both_zero:
+; CHECK-NEXT:    call void @foo(i1 true)
+; CHECK-NEXT:    call void @foo(i1 true)
+; CHECK-NEXT:    call void @bar(i32 0)
+; CHECK-NEXT:    call void @bar(i32 0)
+; CHECK-NEXT:    ret void
+; CHECK:       nope:
+; CHECK-NEXT:    call void @foo(i1 false)
+; CHECK-NEXT:    ret void
+;
   %xz = icmp eq i32 %x, 0
   %yz = icmp eq i32 %y, 0
   %z = and i1 %xz, %yz
   br i1 %z, label %both_zero, label %nope
 both_zero:
   call void @foo(i1 %xz)
-; CHECK: call void @foo(i1 true)
   call void @foo(i1 %yz)
-; CHECK: call void @foo(i1 true)
   call void @bar(i32 %x)
-; CHECK: call void @bar(i32 0)
   call void @bar(i32 %y)
-; CHECK: call void @bar(i32 0)
   ret void
 nope:
   call void @foo(i1 %z)
-; CHECK: call void @foo(i1 false)
+  ret void
+}
+define void @test4(i1 %b, i32 %x) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:    br i1 [[B:%.*]], label [[SW:%.*]], label [[CASE3:%.*]]
+; CHECK:       sw:
+; CHECK-NEXT:    switch i32 [[X:%.*]], label [[DEFAULT:%.*]] [
+; CHECK-NEXT:    i32 0, label [[CASE0:%.*]]
+; CHECK-NEXT:    i32 1, label [[CASE1:%.*]]
+; CHECK-NEXT:    i32 2, label [[CASE0]]
+; CHECK-NEXT:    i32 3, label [[CASE3]]
+; CHECK-NEXT:    i32 4, label [[DEFAULT]]
+; CHECK-NEXT:    ]
+; CHECK:       default:
+; CHECK-NEXT:    call void @bar(i32 [[X]])
+; CHECK-NEXT:    ret void
+; CHECK:       case0:
+; CHECK-NEXT:    call void @bar(i32 [[X]])
+; CHECK-NEXT:    ret void
+; CHECK:       case1:
+; CHECK-NEXT:    call void @bar(i32 1)
+; CHECK-NEXT:    ret void
+; CHECK:       case3:
+; CHECK-NEXT:    call void @bar(i32 [[X]])
+; CHECK-NEXT:    ret void
+;
+  br i1 %b, label %sw, label %case3
+sw:
+  switch i32 %x, label %default [
+  i32 0, label %case0
+  i32 1, label %case1
+  i32 2, label %case0
+  i32 3, label %case3
+  i32 4, label %default
+  ]
+default:
+  call void @bar(i32 %x)
+  ret void
+case0:
+  call void @bar(i32 %x)
+  ret void
+case1:
+  call void @bar(i32 %x)
+  ret void
+case3:
+  call void @bar(i32 %x)
   ret void
 }
 
-; CHECK-LABEL: @test5(
 define i1 @test5(i32 %x, i32 %y) {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
+; CHECK:       same:
+; CHECK-NEXT:    ret i1 false
+; CHECK:       different:
+; CHECK-NEXT:    ret i1 false
+;
   %cmp = icmp eq i32 %x, %y
   br i1 %cmp, label %same, label %different
 
 same:
   %cmp2 = icmp ne i32 %x, %y
-; CHECK: ret i1 false
   ret i1 %cmp2
 
 different:
   %cmp3 = icmp eq i32 %x, %y
-; CHECK: ret i1 false
   ret i1 %cmp3
 }
 
 
-; CHECK-LABEL: @test7(
 define i1 @test7(i32 %x, i32 %y) {
+; CHECK-LABEL: @test7(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
+; CHECK:       same:
+; CHECK-NEXT:    ret i1 false
+; CHECK:       different:
+; CHECK-NEXT:    ret i1 false
+;
   %cmp = icmp sgt i32 %x, %y
   br i1 %cmp, label %same, label %different
 
 same:
   %cmp2 = icmp sle i32 %x, %y
-; CHECK: ret i1 false
   ret i1 %cmp2
 
 different:
   %cmp3 = icmp sgt i32 %x, %y
-; CHECK: ret i1 false
   ret i1 %cmp3
 }
 
-; CHECK-LABEL: @test7_fp(
 define i1 @test7_fp(float %x, float %y) {
+; CHECK-LABEL: @test7_fp(
+; CHECK-NEXT:    [[CMP:%.*]] = fcmp ogt float [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
+; CHECK:       same:
+; CHECK-NEXT:    ret i1 false
+; CHECK:       different:
+; CHECK-NEXT:    ret i1 false
+;
   %cmp = fcmp ogt float %x, %y
   br i1 %cmp, label %same, label %different
 
 same:
   %cmp2 = fcmp ule float %x, %y
-; CHECK: ret i1 false
   ret i1 %cmp2
 
 different:
   %cmp3 = fcmp ogt float %x, %y
-; CHECK: ret i1 false
   ret i1 %cmp3
 }
 
 ; PR1768
-; CHECK-LABEL: @test9(
 define i32 @test9(i32 %i, i32 %j) {
+; CHECK-LABEL: @test9(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[I:%.*]], [[J:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[RET:%.*]]
+; CHECK:       cond_true:
+; CHECK-NEXT:    ret i32 0
+; CHECK:       ret:
+; CHECK-NEXT:    ret i32 5
+;
   %cmp = icmp eq i32 %i, %j
   br i1 %cmp, label %cond_true, label %ret
 
 cond_true:
   %diff = sub i32 %i, %j
   ret i32 %diff
-; CHECK: ret i32 0
 
 ret:
   ret i32 5
-; CHECK: ret i32 5
 }
 
 ; PR1768
-; CHECK-LABEL: @test10(
 define i32 @test10(i32 %j, i32 %i) {
+; CHECK-LABEL: @test10(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[I:%.*]], [[J:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[RET:%.*]]
+; CHECK:       cond_true:
+; CHECK-NEXT:    ret i32 0
+; CHECK:       ret:
+; CHECK-NEXT:    ret i32 5
+;
   %cmp = icmp eq i32 %i, %j
   br i1 %cmp, label %cond_true, label %ret
 
 cond_true:
   %diff = sub i32 %i, %j
   ret i32 %diff
-; CHECK: ret i32 0
 
 ret:
   ret i32 5
-; CHECK: ret i32 5
 }
 
 declare i32 @yogibar()
 
-; CHECK-LABEL: @test11(
 define i32 @test11(i32 %x) {
+; CHECK-LABEL: @test11(
+; CHECK-NEXT:    [[V0:%.*]] = call i32 @yogibar()
+; CHECK-NEXT:    [[V1:%.*]] = call i32 @yogibar()
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[V0]], [[V1]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[NEXT:%.*]]
+; CHECK:       cond_true:
+; CHECK-NEXT:    ret i32 [[V0]]
+; CHECK:       next:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[X:%.*]], [[V0]]
+; CHECK-NEXT:    br i1 [[CMP2]], label [[COND_TRUE2:%.*]], label [[NEXT2:%.*]]
+; CHECK:       cond_true2:
+; CHECK-NEXT:    ret i32 [[X]]
+; CHECK:       next2:
+; CHECK-NEXT:    ret i32 0
+;
   %v0 = call i32 @yogibar()
   %v1 = call i32 @yogibar()
   %cmp = icmp eq i32 %v0, %v1
   br i1 %cmp, label %cond_true, label %next
 
 cond_true:
   ret i32 %v1
-; CHECK: ret i32 %v0
 
 next:
   %cmp2 = icmp eq i32 %x, %v0
   br i1 %cmp2, label %cond_true2, label %next2
 
 cond_true2:
   ret i32 %v0
-; CHECK: ret i32 %x
 
 next2:
   ret i32 0
 }
 
-; CHECK-LABEL: @test12(
 define i32 @test12(i32 %x) {
+; CHECK-LABEL: @test12(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_FALSE:%.*]]
+; CHECK:       cond_true:
+; CHECK-NEXT:    br label [[RET:%.*]]
+; CHECK:       cond_false:
+; CHECK-NEXT:    br label [[RET]]
+; CHECK:       ret:
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ 0, [[COND_TRUE]] ], [ [[X]], [[COND_FALSE]] ]
+; CHECK-NEXT:    ret i32 [[RES]]
+;
   %cmp = icmp eq i32 %x, 0
   br i1 %cmp, label %cond_true, label %cond_false
 
 cond_true:
   br label %ret
 
 cond_false:
   br label %ret
 
 ret:
   %res = phi i32 [ %x, %cond_true ], [ %x, %cond_false ]
-; CHECK: %res = phi i32 [ 0, %cond_true ], [ %x, %cond_false ]
   ret i32 %res
 }

llvm/trunk/test/Transforms/NewGVN/edge.ll

-; XFAIL: *
 ; RUN: opt -newgvn -S < %s | FileCheck %s
 
 define i32 @f1(i32 %x) {
   ; CHECK-LABEL: define i32 @f1(
 bb0:
   %cmp = icmp eq i32 %x, 0
   br i1 %cmp, label %bb2, label %bb1
 bb1:

llvm/trunk/test/Transforms/Util/PredicateInfo/condprop.ll

nope:
   call void @foo(i1 %z)
   ret void
 }
 
 define void @test4(i1 %b, i32 %x) {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[SW:%.*]], label [[CASE3:%.*]]
 ; CHECK:       sw:
-; CHECK-NEXT:    switch i32 [[X:%.*]], label [[DEFAULT:%.*]] [
-; CHECK-NEXT:    i32 0, label [[CASE0:%.*]]
+; CHECK:         i32 0, label [[CASE0:%.*]]
 ; CHECK-NEXT:    i32 1, label [[CASE1:%.*]]
 ; CHECK-NEXT:    i32 2, label [[CASE0]]
 ; CHECK-NEXT:    i32 3, label [[CASE3]]
+; CHECK-NEXT:    i32 4, label [[DEFAULT:%.*]]
+; CHECK-NEXT:    ] Edge: [label [[SW]],label %case1] }
+; CHECK-NEXT:    [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X:%.*]])
+; CHECK-NEXT:    switch i32 [[X]], label [[DEFAULT]] [
+; CHECK-NEXT:    i32 0, label [[CASE0]]
+; CHECK-NEXT:    i32 1, label [[CASE1]]
+; CHECK-NEXT:    i32 2, label [[CASE0]]
+; CHECK-NEXT:    i32 3, label [[CASE3]]
 ; CHECK-NEXT:    i32 4, label [[DEFAULT]]
 ; CHECK-NEXT:    ]
 ; CHECK:       default:
 ; CHECK-NEXT:    call void @bar(i32 [[X]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       case0:
 ; CHECK-NEXT:    call void @bar(i32 [[X]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       case1:
-; CHECK-NEXT:    call void @bar(i32 [[X]])
+; CHECK-NEXT:    call void @bar(i32 [[X_0]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       case3:
 ; CHECK-NEXT:    call void @bar(i32 [[X]])
 ; CHECK-NEXT:    ret void
 ;
   br i1 %b, label %sw, label %case3
 sw:
   switch i32 %x, label %default [

llvm/trunk/test/Transforms/Util/PredicateInfo/edge.ll

bb2:
   %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ]
   %foo = add i32 %cond, %x
   ret i32 %foo
 }
 
 define i32 @f3(i32 %x) {
 ; CHECK-LABEL: @f3(
 ; CHECK-NEXT:  bb0:
-; CHECK-NEXT:    switch i32 [[X:%.*]], label [[BB1:%.*]] [
+; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X:%.*]])
+; CHECK-NEXT:    switch i32 [[X]], label [[BB1:%.*]] [
 ; CHECK-NEXT:    i32 0, label [[BB2:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB2]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[X]], [[BB0:%.*]] ], [ 0, [[BB1]] ]
+; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[X_0]], [[BB0:%.*]] ], [ 0, [[BB1]] ]
 ; CHECK-NEXT:    [[FOO:%.*]] = add i32 [[COND]], [[X]]
 ; CHECK-NEXT:    ret i32 [[FOO]]
 ;
 bb0:
   switch i32 %x, label %bb1 [ i32 0, label %bb2]
 bb1:
   br label %bb2
 bb2: