Add predicateinfo intrinsic, analysis pass, and basic NewGVN support

[• dberlin]

Summary

I'll split this patch up for review, just starting a discussion and
putting something people can play with.

This patch adds a pass to build extended SSA (see "ABCD: eliminating
array bounds checks on demand"), and an intrinsic to support it. This
is then used to get functionality equivalent to propagateEquality in
GVN, in NewGVN (without having to replace instructions as we go). It
would work similarly in SCCP or other passes. This has been talked
about a few times, so i built a real implementation and tried to
productionize it.

The intrinsic is essentially a copy intrinsic which the passes uses to
attach data to (depending on what predicates apply). It is marked as
readnone and returning it's first argument (which is the operand it's
a copy of).

Copies are inserted for operands used in assumes and conditional
branches that are based on comparisons (see below for more)

Every use affected by the predicate is renamed to the appropriate
intrinsic result.

E.g.
%cmp = icmp eq i32 %x, 50
br i1 %cmp, label %true, label %false
true:
ret i32 %x
false:
ret i32 1

will become

%cmp = icmp eq i32, %x, 50
br i1 %cmp, label %true, label %false
true:
; Has predicate info
; branch predicate info { TrueEdge: 1 Comparison: %cmp = icmp eq i32 %x, 50 }
%x.0 = call @llvm.predicateinfo.i32(i32 %x)
ret i32 %x.0
false:
ret i23 1

(you can use -print-predicateinfo to get an annotated-with-predicateinfo dump)

This enables us to easily determine what operations are affected by a
given predicate, and how operations affected by a chain of
predicates.

The intrinsic, marked as returning it's first argument, has no code
generation effect (though currently not every optimization pass knows
that intrinsics with the returned attribute can be looked through).

We deliberately do not attach any info through a second operand so
that the intrinsics do not need to dominate the comparisons/etc (since
in the case of assume, we may want to push them up the post-dominator
tree)

The actual pass stores data about each renamed operand. For operands
used in comparisons in branches, it stores what edge you are in (true
or false), the original comparison, and both parts of the branch edge
(IE the branch block and the successor block for this edge). This is
done so they can be moved without worrying and we can detect they are
invalid. For operands renamed due to assumes, we store where the
assume is.

The pass does not do insertions in blocks unless the operand with
predicateinfo is used there.

(see the false edge above)

Time wise, the pass is O(defs+uses of operands of branch ending
comparisons/assumes). For a CFG that contains 2 million blocks and 1
million icmps, it takes 600ms to insert predicate info. The largest
amount of time is acutally spent in the depth first iterator walking
the dominator tree and inserting blocks into the visited set (which is
a waste of time since it's a tree, sadly). Most passes simply crash
on this file :) Renaming uses takes about 150ms. (timing on most
normal testcases is not really measurable)

We could make it possible to insert only for certain operations if we
want, and at least what i've seen so far, it would be fast enough to
not worry horribly about. Given how fast it is, I have not worried
about updating. Currently, NewGVN nowunderstands the returned
attribute, so it destroys them all. Also as mentioned, we can detect
if they've been invalidated by being moved. Just moving them would
not actually invalidate them (since they have all the info in them
necessary to give correct answers), the only thing that actually would
make them do something bad would be to add uses of them that *aren't*
dominated by one of the edges.

Note that if we decide we don't want to go this direction for some
reason, i would likely make this private to NewGVN or something (i
have another way to do what it does, but it's not as nice).

We also may want to centralize some of the knowledge about what things
imply what (IE have "getConstantValue" or "getEquivalentNames" or
various things, otherwise people have to use isTrueWhenEqual and
isImpliedTrue, everywhere. We have a bunch of missed opt reports about
the places that try to do this but don't catch every case, etc).

[sanjoy]

Just moving them would not actually invalidate them (since they have all the info in them necessary to give correct answers)

Wouldn't speculating them be a problem? That is:

int x = ...;
if (0 s< x s< 20) {
  x_ = predicate_info(x) // attached icmp 0 s< x s< 20
  r0 = 1 / (x_ + 1);
  print r0;
}

to

int x = ...;
x_ = predicate_info(x) // attached icmp 0 s< x s< 20
if (0 s< x s< 20) {
  r0 = 1 / (x_ + 1);
  print r0;
}

to (division safe to speculate since it divides by [1, 20) + 1 =
[2, 21)):

int x = ...;
x_ = predicate_info(x) // attached icmp 0 s< x s< 20
r0 = 1 / (x_ + 1);
if (0 s< x s< 20) {
  print r0;
}

but now you could divide by zero if x was -1.

Generally, (as I've mentioned on IRC) the only concern I had with this was the compile time hit we may have because of the extra dereferences that will now be necessary to go from a use to its "true" operand.

[sanjoy]

In D29316#661376, @sanjoy wrote:

Generally, (as I've mentioned on IRC) the only concern I had with this was the compile time hit we may have because of the extra dereferences that will now be necessary to go from a use to its "true" operand.

Noticed a potential ambiguity here -- I meant going from a use to the value that use actually uses, skipping all of the intermediate predicate_info calls in the use chain.

[• dberlin]

• Remove dead code for placing single argument phi nodes

[• dberlin]

In D29316#661376, @sanjoy wrote:

Just moving them would not actually invalidate them (since they have all the info in them necessary to give correct answers)

Wouldn't speculating them be a problem? That is:

int x = ...;
if (0 s< x s< 20) {
  x_ = predicate_info(x) // attached icmp 0 s< x s< 20
  r0 = 1 / (x_ + 1);
  print r0;
}

to

int x = ...;
x_ = predicate_info(x) // attached icmp 0 s< x s< 20
if (0 s< x s< 20) {
  r0 = 1 / (x_ + 1);
  print r0;
}

It actually knows it belongs inside the if block, it stores the branch block and successor block it belonged to in the info. They are placed at very specific points, so it's also possible to make the retrieval function verify they have not been moved before returning info (IE it can choose to either not give an answer, or determine the answer is still valid). We could do this in passes that may move them.

(Probably not return an answer).

So in your above case, if you did this, we would say nothing, and it becomes equivalent to what it was before.

The bigger problem right now is that nothing is looking through the returned intrinsic, but i can easily fix that in any pass we add predicateinfo to.

Generally, (as I've mentioned on IRC) the only concern I had with this was the compile time hit we may have because of the extra dereferences that will now be necessary to go from a use to its "true" operand.

Sure, which is why, for the moment, i'd probably start by cleaning up our existing usage of this type of info where possible, rather than just add it in new places.

Generally, our passes are based on algorithms that assume a single ssa "name" (for those not familiar, these are not names in llvm, but it's easier to talk about names and values than Value and values :P) has a single value that can be determined across the function.

To handle the cases predicateinfo handles (IE where this is not true), they generally take one of a few approaches:

1. They eagerly try to discover and propagate this info by replacing uses (This is used in part by GVN and EarlyCSE). This tradeoff makes them unsuitable to be used as analysis, and hard to use on any sub-portion of the CFG
2. They maintain complex data structures that try to say what the value of a given name is in different blocks. This is often expensive to maintain (scoped hash tables, which have to be rebuilt each time due to popping scopes), or expensive to do lookups in (log n if it's an interval tree of dfs numbers, whereas gvn's findleader takes O(N)). Sometimes, they maintain multiple ones of these, in conjunction with #1 (GVN is worse than earlycse here).

I tried this approach in NewGVN on a branch, and it's ... a mess to do as an analysis.

3. They try to compute the info lazily to avoid the problems of #1 and #2. This is expensive in a different way.
4. They do nothing, and get worse results (SCCP takes this approach)

The reason, btw, they have to do #1 and #2 at the same time is to handle simple cases like this:

define i32 @test1(i32 %x) {
    %cmp = icmp eq i32 %x, 50
    br i1 %cmp, label %true, label %false
true:
    ret i32 %x
false:
    ret i32 1
}

%x has a different value in the true block, but has no name for that value. So either they have to do eager replacement, or analysis and then separate lookups for each use + general instruction rewriting :(
They all choose the former because the latter is expensive.
With predicateinfo, there is a new name there, so you don't have to do either.
The main cases predicateinfo doesn't get are critical edge cases (which are fixable)

If we can cleanup a bunch of the existing approaches without compile time loss, it's IMHO a win even if we compute it a few times and don't update it.

[davide]

Before I review, some quick comments/questions.

In D29316#663624, @dberlin wrote:

In D29316#661376, @sanjoy wrote:

Just moving them would not actually invalidate them (since they have all the info in them necessary to give correct answers)

Wouldn't speculating them be a problem? That is:

int x = ...;
if (0 s< x s< 20) {
  x_ = predicate_info(x) // attached icmp 0 s< x s< 20
  r0 = 1 / (x_ + 1);
  print r0;
}

to

int x = ...;
x_ = predicate_info(x) // attached icmp 0 s< x s< 20
if (0 s< x s< 20) {
  r0 = 1 / (x_ + 1);
  print r0;
}

It actually knows it belongs inside the if block, it stores the branch block and successor block it belonged to in the info. They are placed at very specific points, so it's also possible to make the retrieval function verify they have not been moved before returning info (IE it can choose to either not give an answer, or determine the answer is still valid). We could do this in passes that may move them.

(Probably not return an answer).

So in your above case, if you did this, we would say nothing, and it becomes equivalent to what it was before.

The bigger problem right now is that nothing is looking through the returned intrinsic, but i can easily fix that in any pass we add predicateinfo to.

Generally, (as I've mentioned on IRC) the only concern I had with this was the compile time hit we may have because of the extra dereferences that will now be necessary to go from a use to its "true" operand.

Sure, which is why, for the moment, i'd probably start by cleaning up our existing usage of this type of info where possible, rather than just add it in new places.

I agree.

Generally, our passes are based on algorithms that assume a single ssa "name" (for those not familiar, these are not names in llvm, but it's easier to talk about names and values than Value and values :P) has a single value that can be determined across the function.

To handle the cases predicateinfo handles (IE where this is not true), they generally take one of a few approaches:

1. They eagerly try to discover and propagate this info by replacing uses (This is used in part by GVN and EarlyCSE). This tradeoff makes them unsuitable to be used as analysis, and hard to use on any sub-portion of the CFG
2. They maintain complex data structures that try to say what the value of a given name is in different blocks. This is often expensive to maintain (scoped hash tables, which have to be rebuilt each time due to popping scopes), or expensive to do lookups in (log n if it's an interval tree of dfs numbers, whereas gvn's findleader takes O(N)). Sometimes, they maintain multiple ones of these, in conjunction with #1 (GVN is worse than earlycse here).

I tried this approach in NewGVN on a branch, and it's ... a mess to do as an analysis.

3. They try to compute the info lazily to avoid the problems of #1 and #2. This is expensive in a different way.

Are you thinking about CVP?

4. They do nothing, and get worse results (SCCP takes this approach)

I really think SCCP should learn about this.

The reason, btw, they have to do #1 and #2 at the same time is to handle simple cases like this:

define i32 @test1(i32 %x) {
    %cmp = icmp eq i32 %x, 50
    br i1 %cmp, label %true, label %false
true:
    ret i32 %x
false:
    ret i32 1
}

%x has a different value in the true block, but has no name for that value. So either they have to do eager replacement, or analysis and then separate lookups for each use + general instruction rewriting :(
They all choose the former because the latter is expensive.
With predicateinfo, there is a new name there, so you don't have to do either.
The main cases predicateinfo doesn't get are critical edge cases (which are fixable)

If we can cleanup a bunch of the existing approaches without compile time loss, it's IMHO a win even if we compute it a few times and don't update it.

[silvas]

One key issue here is that this analysis mutates the IR, which is rarely done in LLVM, and I think we are trying to remove all cases of doing that (as Chandler puts it in http://llvm.org/devmtg/2014-04/PDFs/Talks/Passes.pdf slide 17 "Forms a new, sub-set IR, which is problematic"). On that point, you probably want to start a discussion on LLVMdev (with a link to this review). I anticipate at least Chandler is going to have something to say about this w.r.t the new PM, so make sure to CC him.

In D29316#663624, @dberlin wrote:

Sure, which is why, for the moment, i'd probably start by cleaning up our existing usage of this type of info where possible, rather than just add it in new places.

Generally, our passes are based on algorithms that assume a single ssa "name" (for those not familiar, these are not names in llvm, but it's easier to talk about names and values than Value and values :P) has a single value that can be determined across the function.

To handle the cases predicateinfo handles (IE where this is not true), they generally take one of a few approaches:

1. They eagerly try to discover and propagate this info by replacing uses (This is used in part by GVN and EarlyCSE). This tradeoff makes them unsuitable to be used as analysis, and hard to use on any sub-portion of the CFG
2. They maintain complex data structures that try to say what the value of a given name is in different blocks. This is often expensive to maintain (scoped hash tables, which have to be rebuilt each time due to popping scopes), or expensive to do lookups in (log n if it's an interval tree of dfs numbers, whereas gvn's findleader takes O(N)). Sometimes, they maintain multiple ones of these, in conjunction with #1 (GVN is worse than earlycse here).

I tried this approach in NewGVN on a branch, and it's ... a mess to do as an analysis.

I'm glad to hear that your tried this. My understanding is that traditionally in LLVM we try to keep things inferred from the IR cached in analyses (and only using explicit annotations for things coming in from the frontend). But it seems that what you are saying is that this is really nontrivial to do in this case, with the crux being that you need a primitive for creating a new SSA name to sparsely maintain the information you need (with the rest cached in the analysis). I think it would be better to call the intrinsic "new ssa name" or something which focuses on the primitive mechanism it is providing, rather than one user (can't think of other users off the top of my head though, though I haven't tried very hard). Still, the issue of mutating the IR to insert these new SSA names is quite thorny and deserves a thread on llvm-dev IMO; this use case seems pretty compelling.

[• dberlin]

In D29316#664303, @silvas wrote:

One key issue here is that this analysis mutates the IR, which is rarely done in LLVM, and I think we are trying to remove all cases of doing that (as Chandler puts it in http://llvm.org/devmtg/2014-04/PDFs/Talks/Passes.pdf slide 17 "Forms a new, sub-set IR, which is problematic"). On that point, you probably want to start a discussion on LLVMdev (with a link to this review). I anticipate at least Chandler is going to have something to say about this w.r.t the new PM, so make sure to CC him.

Done

In D29316#663624, @dberlin wrote:

Sure, which is why, for the moment, i'd probably start by cleaning up our existing usage of this type of info where possible, rather than just add it in new places.

Generally, our passes are based on algorithms that assume a single ssa "name" (for those not familiar, these are not names in llvm, but it's easier to talk about names and values than Value and values :P) has a single value that can be determined across the function.

To handle the cases predicateinfo handles (IE where this is not true), they generally take one of a few approaches:

1. They eagerly try to discover and propagate this info by replacing uses (This is used in part by GVN and EarlyCSE). This tradeoff makes them unsuitable to be used as analysis, and hard to use on any sub-portion of the CFG
2. They maintain complex data structures that try to say what the value of a given name is in different blocks. This is often expensive to maintain (scoped hash tables, which have to be rebuilt each time due to popping scopes), or expensive to do lookups in (log n if it's an interval tree of dfs numbers, whereas gvn's findleader takes O(N)). Sometimes, they maintain multiple ones of these, in conjunction with #1 (GVN is worse than earlycse here).

I tried this approach in NewGVN on a branch, and it's ... a mess to do as an analysis.

I'm glad to hear that your tried this. My understanding is that traditionally in LLVM we try to keep things inferred from the IR cached in analyses (and only using explicit annotations for things coming in from the frontend).

IMHO, this has turned out to be a bad strategy for a number of things, and a good one for others.
I don't think we should pretend it is the right tradeoff for everything.

But it seems that what you are saying is that this is really nontrivial to do in this case, with the crux being that you need a primitive for creating a new SSA name to sparsely maintain the information you need (with the rest cached in the analysis). I think it would be better to call the intrinsic "new ssa name" or something which focuses on the primitive mechanism it is providing, rather than one user (can't think of other users off the top of my head though, though I haven't tried very hard). Still, the issue of mutating the IR to insert these new SSA names is quite thorny and deserves a thread on llvm-dev IMO; this use case seems pretty compelling.

Would you feel the same way if i just made it a pass or a utility?

We have plenty of both that are required that mutate the IR.
(like, for example, LCSSA)
The reason it's not a pass is because passes can't return results from pass.
It could be a utility, right up until we try to decide we want to update it.

ATM, it's fast enough i don't think we have to do that, but it's hard to predict the future.
Truthfully, on the large cfg testcase, most things take 10+ minutes, and we take 600ms.
(dominators takes about the same).
I'm not sure we could really make it faster through updating, we'd just avoid invalidation since most changes are non-destructive.

[Prazek]

minor fixes

include/llvm/Transforms/Utils/PredicateInfo.h

157–158

redundant.

245

take unique_ptr by value. This ensures that the pointer value sinks (and it is also less characters to read, and it is easier for the optimizer to optimize it)

lib/Transforms/Scalar/NewGVN.cpp

1124

auto *

lib/Transforms/Utils/PredicateInfo.cpp

87–88

Is it ok here to copy the map?

135–136

auto

261

auto

557

extra line betwwen

558–559

Why just not store unique_ptrs inside the map?

[• dberlin]

lib/Transforms/Utils/PredicateInfo.cpp

87–88

No.We really don't want it copying the map

558–559

Yeah, i'll fix it.

[• dberlin]

include/llvm/Transforms/Utils/PredicateInfo.h

245

This does not actually work, afaict.
If you try it, it does not compile no matter what because unique ptrs can't be copied by value, only moved.

If you want me to do something here, exact code appreciated.

This is also a direct copy of the idiom we are using in other analysis passes :)

lib/Transforms/Scalar/NewGVN.cpp

1124

As the summary says, this part of code is mainly here so folks can play with it.
I plan on submitting the newgvn changes separately from the rest, and will clean them up prior to submission.

[• dberlin]

• Remove dead code for placing single argument phi nodes
• Fix some merge errors
• Update for review comments

[• dberlin]

• Move from Analysis to utility
• NewGVN: Don't merge metadata when replacing predicateinfo with original operand

[• dberlin]

About to abandon this in favor of split patches.

[Prazek]

lib/Transforms/Utils/PredicateInfo.cpp

87–88

I will have to look at it later. It looks a little bit suspisous, that this class modifies a map that it doesn't own, doing it in const method. It is just something that I would not expect from name like this.

Is this map used after using this class? I haven't checked it, but if it worked with copying, then probably not, which means that this map could be taken by &&, and own it, without copying.

[Prazek]

include/llvm/Transforms/Utils/PredicateInfo.h

245

I am not sure if the code dissapeard, but code like this:

void take(std::unique_ptr<int> p) {
}


void push() {
  std::unique_ptr<int> a;

  take(std::move(a));
}

Compiles fine, so I would guess it should work, but I will check it with your next reviews.

docs/LangRef.rst

 used by the ``llvm.assume`` intrinsic in order to preserve the instructions
 only used to form the intrinsic's input argument. This might prove undesirable
 if the extra information provided by the ``llvm.assume`` intrinsic does not cause
 sufficient overall improvement in code quality. For this reason,
 ``llvm.assume`` should not be used to document basic mathematical invariants
 that the optimizer can otherwise deduce or facts that are of little use to the
 optimizer.
 
+.. _int_predicateinfo:
+
+'``llvm.predicateinfo``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+::
+
+      declare type @llvm.predicateinfo(type %operand) returned(1) readnone
+
+Arguments:
+""""""""""
+
+The first argument is an operand to which predicate info is attached.
+
+Overview:
+""""""""""
+
+The ``llvm.predicateinfo`` intrinsic is used to attach information to
+operations used in comparisons, as well as to the results of those
+comparisons.  It is a copy operation used to build Extended SSA form,
+and so is placed at the beginning of blocks dominated by the true or
+false edges of branches, as well as blocks that are post-dominated by
+assume operations.
+
+For operations used in branch comparisons, the information attached to
+the intrinsic includes which edge direction the current block is
+dominated by (true or false), as well as the original comparison. For
+assumes, the information attached includes a pointer to the assume
+instruction.
+
+The PredicateInfo analysis can be used to retrieve the attached
+information.  The intrinsic has no code-generation effect, and always
+returns the first argument from the perspective of the optimizer.
+
 .. _type.test:
 
 '``llvm.type.test``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 

include/llvm/IR/Intrinsics.td

 //
 
 def int_memcpy_element_atomic  : Intrinsic<[],
                                            [llvm_anyptr_ty, llvm_anyptr_ty,
                                             llvm_i64_ty, llvm_i32_ty],
                                  [IntrArgMemOnly, NoCapture<0>, NoCapture<1>,
                                   WriteOnly<0>, ReadOnly<1>]>;
 
+//===----- Intrinsics that are used to provide predicate information -----===//
+
+def int_predicateinfo : Intrinsic<[llvm_any_ty], [LLVMMatchType<0>],
+          [IntrNoMem, Returned<0>]>;
 //===----------------------------------------------------------------------===//
 // Target-specific intrinsics
 //===----------------------------------------------------------------------===//
 
 include "llvm/IR/IntrinsicsPowerPC.td"
 include "llvm/IR/IntrinsicsX86.td"
 include "llvm/IR/IntrinsicsARM.td"
 include "llvm/IR/IntrinsicsAArch64.td"
 include "llvm/IR/IntrinsicsXCore.td"
 include "llvm/IR/IntrinsicsHexagon.td"
 include "llvm/IR/IntrinsicsNVVM.td"
 include "llvm/IR/IntrinsicsMips.td"
 include "llvm/IR/IntrinsicsAMDGPU.td"
 include "llvm/IR/IntrinsicsBPF.td"
 include "llvm/IR/IntrinsicsSystemZ.td"
 include "llvm/IR/IntrinsicsWebAssembly.td"

include/llvm/InitializePasses.h

 void initializePostDomOnlyViewerPass(PassRegistry&);
 void initializePostDomPrinterPass(PassRegistry&);
 void initializePostDomViewerPass(PassRegistry&);
 void initializePostDominatorTreeWrapperPassPass(PassRegistry&);
 void initializePostMachineSchedulerPass(PassRegistry&);
 void initializePostOrderFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializePostRAHazardRecognizerPass(PassRegistry&);
 void initializePostRASchedulerPass(PassRegistry&);
+void initializePredicateInfoPrinterLegacyPassPass(PassRegistry &);
 void initializePreISelIntrinsicLoweringLegacyPassPass(PassRegistry&);
 void initializePrintBasicBlockPassPass(PassRegistry&);
 void initializePrintFunctionPassWrapperPass(PassRegistry&);
 void initializePrintModulePassWrapperPass(PassRegistry&);
 void initializeProcessImplicitDefsPass(PassRegistry&);
 void initializeProfileSummaryInfoWrapperPassPass(PassRegistry &);
 void initializePromoteLegacyPassPass(PassRegistry &);
 void initializePruneEHPass(PassRegistry&);

include/llvm/Transforms/Utils/PredicateInfo.h

+//===- PredicateInfo.h - Build PredicateInfo ----------------------*-C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// \file
+// \brief
+//
+// This file implements the PredicateInfo analysis, which creates an Extended
+// SSA form for operations used in branch comparisons and llvm.assume
+// comparisons.  Copies of these operations are inserted into the true/false
+// edge (and after assumes), and information attached to the copies.  All uses
+// of the original operation in blocks dominated by the true/false edge (and
+// assume), are replaced with uses of the copies.  This enables passes to easily
+// and sparsely propagate condition based info into the operations that may be
+// affected.
+//
+// Example:
+// %cmp = icmp eq i32 %x, 50
+// br i1 %cmp, label %true, label %false
+// true:
+// ret i32 %x
+// false:
+// ret i32 1
+//
+// will become
+//
+// %cmp = icmp eq i32, %x, 50
+// br i1 %cmp, label %true, label %false
+// true:
+// %x.0 = call @llvm.predicateinfo.i32(i32 %x)
+// ret i32 %x
+// false:
+// ret i32 1
+//
+// Using getPredicateInfoFor on x.0 will give you the comparison it is
+// dominated by (the icmp), and that you are located in the true edge of that
+// comparison, which tells you x.0 is 50.
+//
+// In order to reduce the number of copies inserted, predicateinfo is only
+// inserted where it would actually be live.  This means if there are no uses of
+// an operation dominated by the branch edges, or by an assume, the associated
+// predicate info is never inserted.
+//
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
+#define LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/ilist.h"
+#include "llvm/ADT/ilist_node.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/OperandTraits.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/Use.h"
+#include "llvm/IR/User.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Pass.h"
+#include "llvm/PassAnalysisSupport.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <algorithm>
+#include <cassert>
+#include <cstddef>
+#include <iterator>
+#include <memory>
+#include <utility>
+
+namespace llvm {
+
+class DominatorTree;
+class Function;
+class Instruction;
+class MemoryAccess;
+class LLVMContext;
+class raw_ostream;
+class OrderedBasicBlock;
+
+enum PredicateType { PT_Branch, PT_Assume };
+
+// 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;
+  Value *OriginalOp;
+  CmpInst *Comparison;
+  // 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.
+  PredicateBase(const PredicateBase &) = delete;
+  PredicateBase &operator=(const PredicateBase &) = delete;
+  PredicateBase() = delete;
+  static inline bool classof(const PredicateBase *) { return true; }
+
+protected:
+  PredicateBase(PredicateType PT, Value *Op, CmpInst *Comparison)
+      : Type(PT), OriginalOp(Op), Comparison(Comparison) {}
+};
+
+// 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 {
+public:
+  IntrinsicInst *AssumeInst;
+  PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, CmpInst *Comparison)
+      : PredicateBase(PT_Assume, Op, Comparison), AssumeInst(AssumeInst) {}
+  PredicateAssume() = delete;
+  static inline bool classof(const PredicateAssume *) { return true; }
+  static inline bool classof(const PredicateBase *PB) {
+    return PB->Type == PT_Assume;
+  }
+};
+
+// Provides predicate information for branches.
+class PredicateBranch : public PredicateBase {
+public:
+  // This is the block that is conditional upon the comparison.
+  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,
+                  CmpInst *Comparison, bool TakenEdge)
+      : PredicateBase(PT_Branch, Op, Comparison), BranchBB(BranchBB),
+        SplitBB(SplitBB), TrueEdge(TakenEdge) {}
+  PredicateBranch() = delete;
+
+  static inline bool classof(const PredicateBranch *) { return true; }
+  static inline bool classof(const PredicateBase *PB) {
+    return PB->Type == PT_Branch;
+  }
+};
+
+// 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 {
+private:
+  // Used to store information about each value we might rename.
+  struct ValueInfo {
+    // Information about each possible copy. During processing, this is each
+    // inserted info. After processing, we move the uninserted ones to the
+    // uninserted vector.
+    SmallVector<PredicateBase *, 4> Infos;
+    SmallVector<PredicateBase *, 4> UninsertedInfos;
+  };
+  // This owns the all the predicate infos in the function, placed or not.
+  iplist<PredicateBase> AllInfos;
+
+public:
+  PredicateInfo(Function &, DominatorTree &, AssumptionCache &);
+  ~PredicateInfo();
+
+  void verifyPredicateInfo() const;
+
+  void dump() const;
+  void print(raw_ostream &) const;
+
+  const PredicateBase *getPredicateInfoFor(const Value *V) const {
+    return PredicateMap.lookup(V);
+  }
+
+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 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 &, int DFSIn, int DFSOut) const;
+  void popStackUntilDFSScope(ValueDFSStack &, int DFSIn, int DFSOut);
+  ValueInfo &getOrCreateValueInfo(Value *);
+  const ValueInfo &getValueInfo(Value *) const;
+  Function &F;
+  DominatorTree &DT;
+  AssumptionCache &AC;
+  // This maps from copy operands to Predicate Info. Note that it does not own
+  // the Predicate Info, they belong to the ValueInfo structs in the ValueInfos
+  // vector.
+  DenseMap<const Value *, const PredicateBase *> PredicateMap;
+  // This stores info about each operand or comparison result we make copies
+  // of.  The real ValueInfos start at index 1, index 0 is unused so that we can
+  // more easily detect invalid indexing.
+  SmallVector<ValueInfo, 32> ValueInfos;
+  // This gives the index into the ValueInfos array for a given Value.  Because
+  // 0 is not a valid Value Info index, you can use DenseMap::lookup and tell
+  // whether it returned a valid result.
+  DenseMap<Value *, unsigned int> ValueInfoNums;
+  // OrderedBasicBlocks used during sorting uses
+  DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> OBBMap;
+};
+
+// This pass does eager building and then printing of PredicateInfo. It is used
+// by
+// the tests to be able to build, dump, and verify PredicateInfo.
+class PredicateInfoPrinterLegacyPass : public FunctionPass {
+public:
+  PredicateInfoPrinterLegacyPass();
+
+  static char ID;
+  bool runOnFunction(Function &) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+};
+
+/// \brief Printer pass for \c PredicateInfo.
+class PredicateInfoPrinterPass
+    : public PassInfoMixin<PredicateInfoPrinterPass> {
+  raw_ostream &OS;
+
+public:
+  explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
+/// \brief Verifier pass for \c PredicateInfo.
+struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> {
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H

lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
 #include "llvm/Transforms/Utils/LCSSA.h"
 #include "llvm/Transforms/Utils/LibCallsShrinkWrap.h"
 #include "llvm/Transforms/Utils/LoopSimplify.h"
 #include "llvm/Transforms/Utils/LowerInvoke.h"
 #include "llvm/Transforms/Utils/Mem2Reg.h"
 #include "llvm/Transforms/Utils/MemorySSA.h"
 #include "llvm/Transforms/Utils/NameAnonGlobals.h"
+#include "llvm/Transforms/Utils/PredicateInfo.h"
 #include "llvm/Transforms/Utils/SimplifyInstructions.h"
 #include "llvm/Transforms/Utils/SymbolRewriter.h"
 #include "llvm/Transforms/Vectorize/LoopVectorize.h"
 #include "llvm/Transforms/Vectorize/SLPVectorizer.h"
 
 #include <type_traits>
 
 using namespace llvm;

lib/Transforms/Scalar/NewGVN.cpp

 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/GVNExpression.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/MemorySSA.h"
+#include "llvm/Transforms/Utils/PredicateInfo.h"
 #include <unordered_map>
 #include <utility>
 #include <vector>
 using namespace llvm;
 using namespace PatternMatch;
 using namespace llvm::GVNExpression;
-
 #define DEBUG_TYPE "newgvn"
 
 STATISTIC(NumGVNInstrDeleted, "Number of instructions deleted");
 STATISTIC(NumGVNBlocksDeleted, "Number of blocks deleted");
 STATISTIC(NumGVNOpsSimplified, "Number of Expressions simplified");
 STATISTIC(NumGVNPhisAllSame, "Number of PHIs whos arguments are all the same");
 STATISTIC(NumGVNMaxIterations,
           "Maximum Number of iterations it took to converge GVN");

 class NewGVN : public FunctionPass {
   DominatorTree *DT;
   const DataLayout *DL;
   const TargetLibraryInfo *TLI;
   AssumptionCache *AC;
   AliasAnalysis *AA;
   MemorySSA *MSSA;
   MemorySSAWalker *MSSAWalker;
+  PredicateInfo *PredInfo;
   BumpPtrAllocator ExpressionAllocator;
   ArrayRecycler<Value *> ArgRecycler;
 
+  // Number of function arguments, used by ranking
+  unsigned int NumFuncArgs;
+
   // Congruence class info.
   CongruenceClass *InitialClass;
   std::vector<CongruenceClass *> CongruenceClasses;
   unsigned NextCongruenceNum;
 
   // Value Mappings.
   DenseMap<Value *, CongruenceClass *> ValueToClass;
   DenseMap<Value *, const Expression *> ValueToExpression;

 
 private:
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     AU.addRequired<MemorySSAWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
-
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
   }
 
   // Expression handling.
   const Expression *createExpression(Instruction *);
   const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *);
   PHIExpression *createPHIExpression(Instruction *);
const Expression *checkSimplificationResults(Expression *, Instruction *,
                                                Value *);
   const Expression *performSymbolicEvaluation(Value *);
   const Expression *performSymbolicLoadEvaluation(Instruction *);
   const Expression *performSymbolicStoreEvaluation(Instruction *);
   const Expression *performSymbolicCallEvaluation(Instruction *);
   const Expression *performSymbolicPHIEvaluation(Instruction *);
   const Expression *performSymbolicAggrValueEvaluation(Instruction *);
   const Expression *performSymbolicCmpEvaluation(Instruction *);
+  const Expression *performSymbolicPredicateInfoEvaluation(Instruction *);
 
   // Congruence finding.
   Value *lookupOperandLeader(Value *) const;
   void performCongruenceFinding(Instruction *, const Expression *);
   void moveValueToNewCongruenceClass(Instruction *, CongruenceClass *,
                                      CongruenceClass *);
   bool setMemoryAccessEquivTo(MemoryAccess *From, CongruenceClass *To);
   MemoryAccess *lookupMemoryAccessEquiv(MemoryAccess *) const;
   bool isMemoryAccessTop(const MemoryAccess *) const;
 
+  // Ranking
+  unsigned int getRank(Value *V) const;
+
   // Reachability handling.
   void updateReachableEdge(BasicBlock *, BasicBlock *);
   void processOutgoingEdges(TerminatorInst *, BasicBlock *);
   bool isOnlyReachableViaThisEdge(const BasicBlockEdge &) const;
   Value *findConditionEquivalence(Value *) const;
 
   // Elimination.
   struct ValueDFS;
const Expression *NewGVN::createExpression(Instruction *I) {
   // IE
   //  add 0, x -> x
   //  and x, x -> x
   // We should handle this by simply rewriting the expression.
   if (auto *CI = dyn_cast<CmpInst>(I)) {
     // Sort the operand value numbers so x<y and y>x get the same value
     // number.
     CmpInst::Predicate Predicate = CI->getPredicate();
-    if (E->getOperand(0) > E->getOperand(1)) {
+    if (getRank(E->getOperand(0)) > getRank(E->getOperand(1))) {
       E->swapOperands(0, 1);
       Predicate = CmpInst::getSwappedPredicate(Predicate);
     }
     E->setOpcode((CI->getOpcode() << 8) | Predicate);
     // TODO: 25% of our time is spent in SimplifyCmpInst with pointer operands
     assert(I->getOperand(0)->getType() == I->getOperand(1)->getType() &&
            "Wrong types on cmp instruction");
     assert((E->getOperand(0)->getType() == I->getOperand(0)->getType() &&
const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I) {
   }
 
   const Expression *E =
       createLoadExpression(LI->getType(), LI->getPointerOperand(), LI,
                            lookupMemoryAccessEquiv(DefiningAccess));
   return E;
 }
 
+const Expression *
+NewGVN::performSymbolicPredicateInfoEvaluation(Instruction *I) {
+  if (auto *PI = PredInfo->getPredicateInfoFor(I)) {
+    DEBUG(dbgs() << "Found predicate info from instruction !\n");
+    auto *CopyOf = I->getOperand(0);
+    auto *Cmp = PI->Comparison;
+    // If this is an assume predicate and a copy of the comparison, it must be
+    // true.
+    if (isa<PredicateAssume>(PI) && CopyOf == Cmp)
+      return createConstantExpression(ConstantInt::getTrue(Cmp->getType()));
+
+    Value *FirstOp = lookupOperandLeader(Cmp->getOperand(0));
+    Value *SecondOp = lookupOperandLeader(Cmp->getOperand(1));
+    // Sort the ops
+    CmpInst::Predicate Predicate = Cmp->getPredicate();
+    // FIXME: We should really be ranking them here
+    if (getRank(FirstOp) > getRank(SecondOp)) {
+      std::swap(FirstOp, SecondOp);
+      Predicate = CmpInst::getSwappedPredicate(Predicate);
+    }
+
+    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))
+        if (auto *C = dyn_cast<Constant>(FirstOp))
+          return createConstantExpression(C);
+      return createVariableExpression(FirstOp);
+    } else if (const auto *PBranch = dyn_cast<PredicateBranch>(PI)) {
+      if (CopyOf == Cmp) {
+        if (CmpInst::isTrueWhenEqual(Predicate)) {
+          if (PBranch->TrueEdge)
+            return createConstantExpression(
+                ConstantInt::getTrue(Cmp->getType()));
+          else
+            return createConstantExpression(
+                ConstantInt::getFalse(Cmp->getType()));
+        } else if (CmpInst::isFalseWhenEqual(Predicate)) {
+          if (!PBranch->TrueEdge)
+            return createConstantExpression(
+                ConstantInt::getTrue(Cmp->getType()));
+          else
+            return createConstantExpression(
+                ConstantInt::getFalse(Cmp->getType()));
+        }
+      } else if ((PBranch->TrueEdge && CmpInst::isTrueWhenEqual(Predicate)) ||
+                 (!PBranch->TrueEdge && CmpInst::isFalseWhenEqual(Predicate))) {
+        if (auto *C = dyn_cast<Constant>(FirstOp))
+          return createConstantExpression(C);
+        return createVariableExpression(FirstOp);
+      } else if (((PBranch->TrueEdge && Predicate == CmpInst::FCMP_OEQ) ||
+                  (!PBranch->TrueEdge && Predicate == CmpInst::FCMP_UNE)) &&
+                 isa<ConstantFP>(FirstOp) &&
+                 !cast<ConstantFP>(FirstOp)->isZero()) {
+        return createConstantExpression(cast<Constant>(FirstOp));
+      }
+    }
+  }
+  return nullptr;
+}
+
 // Evaluate read only and pure calls, and create an expression result.
 const Expression *NewGVN::performSymbolicCallEvaluation(Instruction *I) {
   auto *CI = cast<CallInst>(I);
-  if (AA->doesNotAccessMemory(CI))
+  if (auto *II = dyn_cast<IntrinsicInst>(I)) {
+    // Things with the returned attribute are copies of arguments
+    if (auto *ReturnedValue = II->getReturnedArgOperand()) {
+      if (II->getIntrinsicID() == Intrinsic::predicateinfo) {
+        const Expression *Result = performSymbolicPredicateInfoEvaluation(I);
+        if (Result)
+          return Result;
+      }
+      if (auto *C = dyn_cast<Constant>(ReturnedValue))
+        return createConstantExpression(C);
+      return createVariableExpression(ReturnedValue);
+    }
+  }
+  if (AA->doesNotAccessMemory(CI)) {
     return createCallExpression(CI, nullptr);
-  if (AA->onlyReadsMemory(CI)) {
+  } else if (AA->onlyReadsMemory(CI)) {
     MemoryAccess *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(CI);
     return createCallExpression(CI, lookupMemoryAccessEquiv(DefiningAccess));
   }
   return nullptr;
 }
 
 // Update the memory access equivalence table to say that From is equal to To,
 // and return true if this is different from what already existed in the table.
if (II && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) {
         break;
       }
 
       if (Opcode != 0) {
         // Intrinsic recognized. Grab its args to finish building the
         // expression.
         assert(II->getNumArgOperands() == 2 &&
                "Expect two args for recognised intrinsics.");
-        return createBinaryExpression(Opcode, EI->getType(),
-                                      II->getArgOperand(0),
-                                      II->getArgOperand(1));
+        return createBinaryExpression(
+            Opcode, EI->getType(), II->getArgOperand(0), II->getArgOperand(1));
       }
     }
   }
 
   return createAggregateValueExpression(I);
 }
 const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) {
-  CmpInst *CI = dyn_cast<CmpInst>(I);
-  // See if our operands are equal and that implies something.
+  auto *CI = dyn_cast<CmpInst>(I);
+  // See if our operands are equal to those of a previous predicate, and if so,
+  // if it implies true or false.
   auto Op0 = lookupOperandLeader(CI->getOperand(0));
   auto Op1 = lookupOperandLeader(CI->getOperand(1));
+  // 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()));
+
+  // See if we know something just from the operands themselves
   if (Op0 == Op1) {
     if (CI->isTrueWhenEqual())
       return createConstantExpression(ConstantInt::getTrue(CI->getType()));
     else if (CI->isFalseWhenEqual())
       return createConstantExpression(ConstantInt::getFalse(CI->getType()));
   }
+
+  // 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.
+      //
+      auto *BranchCond = PBranch->Comparison;
+      if (lookupOperandLeader(BranchCond->getOperand(0)) == Op0 &&
+          lookupOperandLeader(BranchCond->getOperand(1)) == Op1) {
+        if (PBranch->TrueEdge) {
+          // If we know the previous predicate is true and we are in the true
+          // edge then we may be implied true or false.
+          if (CI->isImpliedTrueByMatchingCmp(BranchCond->getPredicate()))
+            return createConstantExpression(
+                ConstantInt::getTrue(CI->getType()));
+          if (CI->isImpliedFalseByMatchingCmp(BranchCond->getPredicate()))
+            return createConstantExpression(
+                ConstantInt::getFalse(CI->getType()));
+        } else {
+          // Just handle the ne and eq cases, where if we have the same
+          // operands, we may know something.
+          if (BranchCond->getPredicate() == CI->getPredicate()) {
+            // Same predicate, same ops,we know it was false, so this is false.
+            return createConstantExpression(
+                ConstantInt::getFalse(CI->getType()));
+          } else if (BranchCond->getPredicate() == CI->getInversePredicate()) {
+            // Inverse predicate, we know the other was false, so this is true.
+            // FIXME: Double check this
+            return createConstantExpression(
+                ConstantInt::getTrue(CI->getType()));
+          }
+        }
+      }
+    }
+  }
+  // Create expression will take care of simplifyCmpInst
   return createExpression(I);
 }
 
 // Substitute and symbolize the value before value numbering.
 const Expression *NewGVN::performSymbolicEvaluation(Value *V) {
   const Expression *E = nullptr;
   if (auto *C = dyn_cast<Constant>(V))
     E = createConstantExpression(C);
   else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
     E = createVariableExpression(V);
   } else {
     // TODO: memory intrinsics.
     // TODO: Some day, we should do the forward propagation and reassociation
void NewGVN::verifyMemoryCongruency() const {
   }
 }
 
 // This is the main transformation entry point.
 bool NewGVN::runGVN(Function &F, DominatorTree *_DT, AssumptionCache *_AC,
                     TargetLibraryInfo *_TLI, AliasAnalysis *_AA,
                     MemorySSA *_MSSA) {
   bool Changed = false;
+  NumFuncArgs = F.arg_size();
   DT = _DT;
   AC = _AC;
   TLI = _TLI;
   AA = _AA;
   MSSA = _MSSA;
+  PredInfo = new PredicateInfo(F, *DT, *AC);
   DL = &F.getParent()->getDataLayout();
   MSSAWalker = MSSA->getWalker();
 
   // Count number of instructions for sizing of hash tables, and come
   // up with a global dfs numbering for instructions.
   unsigned ICount = 1;
   // Add an empty instruction to account for the fact that we start at 1
   DFSToInstr.emplace_back(nullptr);
bool NewGVN::runGVN(Function &F, DominatorTree *_DT, AssumptionCache *_AC,
   initializeCongruenceClasses(F);
 
   unsigned int Iterations = 0;
   // We start out in the entry block.
   BasicBlock *LastBlock = &F.getEntryBlock();
   while (TouchedInstructions.any()) {
     ++Iterations;
     // Walk through all the instructions in all the blocks in RPO.
+    // TODO: As we hit a new block, we should push and pop equalities into a
+    // table lookupOperandLeader can use, to catch things PredicateInfo
+    // might miss, like edge-only equivalences.
     for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1;
          InstrNum = TouchedInstructions.find_next(InstrNum)) {
 
       // This instruction was found to be dead. We don't bother looking
       // at it again.
       if (InstrNum == 0) {
         TouchedInstructions.reset(InstrNum);
         continue;
if (alwaysAvailable(Leader)) {
             continue;
 
           DEBUG(dbgs() << "Found replacement " << *Result << " for "
                        << *MemberUse->get() << " in " << *(MemberUse->getUser())
                        << "\n");
 
           // If we replaced something in an instruction, handle the patching of
           // metadata.
-          if (auto *ReplacedInst = dyn_cast<Instruction>(MemberUse->get()))
+          if (auto *ReplacedInst = dyn_cast<Instruction>(MemberUse->get())) {
+            // Skip this if we are replacing predicateinfo with it's original
+            // operand, as we already know we can just drop it.
+            auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst);
+            if (!PI || Result != PI->OriginalOp)
               patchReplacementInstruction(ReplacedInst, Result);
+          }
 
           assert(isa<Instruction>(MemberUse->getUser()));
           MemberUse->set(Result);
           AnythingReplaced = true;
         }
       }
     }
 
if (CC->StoreCount > 0) {
         CC->Members.erase(Member);
         ++NumGVNDeadStores;
       }
     }
   }
 
   return AnythingReplaced;
 }
+
+unsigned int NewGVN::getRank(Value *V) const {
+  if (isa<Constant>(V))
+    return 0;
+  else if (Argument *A = dyn_cast<Argument>(V))
+    return 1 + A->getArgNo();
+
+  // Need to shift the instruction DFS by number of arguments + 1 to account for
+  // the constant and argument ranking above.
+  unsigned Result = InstrDFS.lookup(V);
+  if (Result > 0)
+    return 2 + NumFuncArgs + Result;
+  // Unreachable or something else, just return a really large number.
+  return ~0;
+}

lib/Transforms/Utils/CMakeLists.txt

add_llvm_library(LLVMTransformUtils
   LowerInvoke.cpp
   LowerSwitch.cpp
   Mem2Reg.cpp
   MemorySSA.cpp
   MemorySSAUpdater.cpp
   MetaRenamer.cpp
   ModuleUtils.cpp
   NameAnonGlobals.cpp
+  PredicateInfo.cpp
   PromoteMemoryToRegister.cpp
   StripGCRelocates.cpp
   SSAUpdater.cpp
   SanitizerStats.cpp
   SimplifyCFG.cpp
   SimplifyIndVar.cpp
   SimplifyInstructions.cpp
   SimplifyLibCalls.cpp

lib/Transforms/Utils/PredicateInfo.cpp

+//===-- PredicateInfo.cpp - PredicateInfo Builder--------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------===//
+//
+// This file implements the PredicateInfo class.
+//
+//===----------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/PredicateInfo.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/CFG.h"
+#include "llvm/Analysis/OrderedBasicBlock.h"
+#include "llvm/IR/AssemblyAnnotationWriter.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/GlobalVariable.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Metadata.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/FormattedStream.h"
+#include "llvm/Transforms/Scalar.h"
+#include <algorithm>
+#define DEBUG_TYPE "predicateinfo"
+using namespace llvm;
+using namespace PatternMatch;
+using namespace llvm::PredicateInfoClasses;
+
+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 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.
+  LN_Middle,
+  // Operations that must appear last in a block, like successor phi node uses.
+  LN_Last
+};
+
+// Associate global and local DFS info with defs and uses, so we can sort them
+// into a global domination ordering.
+struct ValueDFS {
+  int DFSIn = 0;
+  int DFSOut = 0;
+  unsigned int LocalNum = LN_Middle;
+  PredicateBase *PInfo = nullptr;
+  // Only one of Def or Use will be set.
+  Value *Def = nullptr;
+  Use *Use = nullptr;
+};
+
+// This compares ValueDFS structures, creating OrderedBasicBlocks where
+// necessary to compare uses/defs in the same block.  Doing so allows us to walk
+// the minimum number of instructions necessary to compute our def/use ordering.
+struct ValueDFS_Compare {
+  DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> &OBBMap;
+  ValueDFS_Compare(
+      DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> &OBBMap)
+      : OBBMap(OBBMap) {}
+  bool operator()(const ValueDFS &A, const ValueDFS &B) const {
+    if (&A == &B)
+      return false;
+    // The only case we can't directly compare them is when they in the same
+    // block, and both have localnum == middle.  In that case, we have to use
+    // comesbefore to see what the real ordering is, because they are in the
+    // same basic block.
+
+    bool SameBlock = std::tie(A.DFSIn, A.DFSOut) == std::tie(B.DFSIn, B.DFSOut);
+
+    if (!SameBlock || A.LocalNum != LN_Middle || B.LocalNum != LN_Middle)
+      return std::tie(A.DFSIn, A.DFSOut, A.LocalNum, A.Def, A.Use) <
+             std::tie(B.DFSIn, B.DFSOut, B.LocalNum, B.Def, B.Use);
+    return localComesBefore(A, B);
+  }
+
+  // This performs the necessary local basic block ordering checks to tell
+  // whether A comes before B, where both are in the same basic block.
+  bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const {
+    auto *ADef = A.Def;
+    auto *BDef = B.Def;
+
+    // It's possible for the defs and uses to be null.  For branches, the local
+    // numbering will say the placed predicaeinfos should go first (IE
+    // LN_beginning), so we won't be in this function. For assumes, we will end
+    // up here, beause we need to order the def we will placerelative to the
+    // assume.  So for the purpose of this function, we pretend the def is the
+    // assume because that is where we will insert the info.
+    if (!ADef && !A.Use) {
+      assert(A.PInfo &&
+             "No def, no use, and no predicateinfo should not occur");
+      assert(isa<PredicateAssume>(A.PInfo) &&
+             "Middle of block should only occur for assumes");
+      ADef = cast<PredicateAssume>(A.PInfo)->AssumeInst;
+    }
+    if (!BDef && !B.Use) {
+      assert(B.PInfo &&
+             "No def, no use, and no predicateinfo should not occur");
+      assert(isa<PredicateAssume>(B.PInfo) &&
+             "Middle of block should only occur for assumes");
+      BDef = cast<PredicateAssume>(B.PInfo)->AssumeInst;
+    }
+
+    // See if we have real values or uses. If we have real values, we are
+    // guaranteed they are instructions or arguments. No matter what, we are
+    // guaranteed they are in the same block if they are instructions.
+    auto *ArgA = dyn_cast_or_null<Argument>(ADef);
+    auto *ArgB = dyn_cast_or_null<Argument>(BDef);
+
+    if (ArgA && !ArgB)
+      return true;
+    if (ArgB && !ArgA)
+      return false;
+    if (ArgA && ArgB)
+      return ArgA->getArgNo() < ArgB->getArgNo();
+
+    Instruction *AInst = nullptr;
+    Instruction *BInst = nullptr;
+    if (ADef) {
+      AInst = cast<Instruction>(ADef);
+    } else {
+      AInst = cast<Instruction>(A.Use->getUser());
+    }
+    if (BDef) {
+      BInst = cast<Instruction>(BDef);
+    } else {
+      BInst = cast<Instruction>(B.Use->getUser());
+    }
+    auto *BB = AInst->getParent();
+    auto LookupResult = OBBMap.find(BB);
+    if (LookupResult != OBBMap.end())
+      return LookupResult->second->dominates(AInst, BInst);
+    else {
+      //      auto *OBB = new OrderedBasicBlock(BB);
+      auto Result = OBBMap.insert({BB, make_unique<OrderedBasicBlock>(BB)});
+      return Result.first->second->dominates(AInst, BInst);
+    }
+    return std::tie(ADef, A.Use) < std::tie(BDef, B.Use);
+  }
+};
+
+} // namespace PredicateInfoClasses
+
+bool PredicateInfo::stackIsInScope(const ValueDFSStack &Stack, int DFSIn,
+                                   int DFSOut) const {
+  if (Stack.empty())
+    return false;
+  return DFSIn >= Stack.back().DFSIn && DFSOut <= Stack.back().DFSOut;
+}
+
+void PredicateInfo::popStackUntilDFSScope(ValueDFSStack &Stack, int DFSIn,
+                                          int DFSOut) {
+  while (!Stack.empty() && !stackIsInScope(Stack, DFSIn, DFSOut))
+    Stack.pop_back();
+}
+
+// Convert the uses of Op into a vector of uses, associating global and local
+// DFS info with each one.
+void PredicateInfo::convertUsesToDFSOrdered(
+    Value *Op, SmallVectorImpl<ValueDFS> &DFSOrderedSet) {
+  for (auto &U : Op->uses()) {
+    if (auto *I = dyn_cast<Instruction>(U.getUser())) {
+      ValueDFS VD;
+      // Put the phi node uses in the incoming block.
+      BasicBlock *IBlock;
+      if (auto *PN = dyn_cast<PHINode>(I)) {
+        IBlock = PN->getIncomingBlock(U);
+        // Make phi node users appear last in the incoming block
+        // they are from.
+        VD.LocalNum = LN_Last;
+      } else {
+        // If it's not a phi node use, it is somewhere in the middle of the
+        // block.
+        IBlock = I->getParent();
+        VD.LocalNum = LN_Middle;
+      }
+      DomTreeNode *DomNode = DT.getNode(IBlock);
+      // It's possible our use is in an unreachable block. Skip it if so.
+      if (!DomNode)
+        continue;
+      VD.DFSIn = DomNode->getDFSNumIn();
+      VD.DFSOut = DomNode->getDFSNumOut();
+      VD.Use = &U;
+      DFSOrderedSet.push_back(VD);
+    }
+  }
+}
+
+// Collect relevant operations from Comparison that we may want to insert copies
+// for.
+void collectCmpOps(CmpInst *Comparison, SmallVectorImpl<Value *> &CmpOperands) {
+  auto *Op0 = Comparison->getOperand(0);
+  auto *Op1 = Comparison->getOperand(1);
+  if (Op0 == Op1)
+    return;
+  CmpOperands.push_back(Comparison);
+  // Only want real values, not constants.  Additionally, operands with one use
+  // are only being used in the comparison, which means they will not be useful
+  // for us to consider for predicateinfo.
+  //
+  // FIXME: LLVM crashes trying to create an intrinsic declaration of some
+  // pointer to function types that return structs, so we avoid them.
+  if ((isa<Instruction>(Op0) || isa<Argument>(Op0)) && !Op0->hasOneUse() &&
+      !(Op0->getType()->isPointerTy() &&
+        Op0->getType()->getPointerElementType()->isFunctionTy()))
+    CmpOperands.push_back(Op0);
+  if ((isa<Instruction>(Op1) || isa<Argument>(Op1)) && !Op1->hasOneUse() &&
+      !(Op1->getType()->isPointerTy() &&
+        Op1->getType()->getPointerElementType()->isFunctionTy()))
+    CmpOperands.push_back(Op1);
+}
+
+// Process an assume instruction and place relevant operations we want to rename
+// into OpsToRename.
+void PredicateInfo::processAssume(IntrinsicInst *II, BasicBlock *AssumeBB,
+                                  SmallPtrSetImpl<Value *> &OpsToRename) {
+  SmallVector<Value *, 8> CmpOperands;
+  // Second, see if we have a comparison we support
+  SmallVector<Value *, 2> ComparisonsToProcess;
+  CmpInst::Predicate Pred;
+  Value *Operand = II->getOperand(0);
+  if (m_c_And(m_Cmp(Pred, m_Value(), m_Value()),
+              m_Cmp(Pred, m_Value(), m_Value()))
+          .match(II->getOperand(0))) {
+    ComparisonsToProcess.push_back(
+        cast<BinaryOperator>(Operand)->getOperand(0));
+    ComparisonsToProcess.push_back(
+        cast<BinaryOperator>(Operand)->getOperand(1));
+  } else {
+    ComparisonsToProcess.push_back(Operand);
+  }
+  for (auto Comparison : ComparisonsToProcess) {
+    if (auto *Cmp = dyn_cast<CmpInst>(Comparison)) {
+      collectCmpOps(Cmp, CmpOperands);
+      // Now add our copy infos for our operands
+      for (auto *Op : CmpOperands) {
+        OpsToRename.insert(Op);
+        auto &OperandInfo = getOrCreateValueInfo(Op);
+        PredicateBase *PB = new PredicateAssume(Op, II, Cmp);
+        AllInfos.push_back(PB);
+        OperandInfo.Infos.push_back(PB);
+      }
+      CmpOperands.clear();
+    }
+  }
+}
+
+// Process a block terminating branch, and place relevant operations to be
+// renamed into OpsToRename.
+void PredicateInfo::processBranch(BranchInst *BI, BasicBlock *BranchBB,
+                                  SmallPtrSetImpl<Value *> &OpsToRename) {
+  SmallVector<Value *, 8> CmpOperands;
+  BasicBlock *FirstBB = BI->getSuccessor(0);
+  BasicBlock *SecondBB = BI->getSuccessor(1);
+  bool FirstSinglePred = FirstBB->getSinglePredecessor();
+  bool SecondSinglePred = SecondBB->getSinglePredecessor();
+  SmallVector<BasicBlock *, 2> SuccsToProcess;
+  // First make sure we have single preds for these successors, as we can't
+  // usefully propagate true/false info to them if there are multiple paths to
+  // them.
+  if (FirstSinglePred)
+    SuccsToProcess.push_back(FirstBB);
+  if (SecondSinglePred)
+    SuccsToProcess.push_back(SecondBB);
+  if (SuccsToProcess.empty())
+    return;
+  // Second, see if we have a comparison we support
+  SmallVector<Value *, 2> ComparisonsToProcess;
+  CmpInst::Predicate Pred;
+
+  // Match combinations of conditions.
+  if (match(BI->getCondition(), m_And(m_Cmp(Pred, m_Value(), m_Value()),
+                                      m_Cmp(Pred, m_Value(), m_Value()))) ||
+      match(BI->getCondition(), m_Or(m_Cmp(Pred, m_Value(), m_Value()),
+                                     m_Cmp(Pred, m_Value(), m_Value())))) {
+    ComparisonsToProcess.push_back(
+        cast<BinaryOperator>(BI->getCondition())->getOperand(0));
+    ComparisonsToProcess.push_back(
+        cast<BinaryOperator>(BI->getCondition())->getOperand(1));
+  } else {
+    ComparisonsToProcess.push_back(BI->getCondition());
+  }
+  for (auto Comparison : ComparisonsToProcess) {
+    if (auto *Cmp = dyn_cast<CmpInst>(Comparison)) {
+      collectCmpOps(Cmp, CmpOperands);
+      // Now add our copy infos for our operands
+      for (auto *Op : CmpOperands) {
+        OpsToRename.insert(Op);
+        auto &OperandInfo = getOrCreateValueInfo(Op);
+        for (auto *Succ : SuccsToProcess) {
+          bool TakenEdge = (Succ == FirstBB);
+          PredicateBase *PB =
+              new PredicateBranch(Op, BranchBB, Succ, Cmp, TakenEdge);
+          AllInfos.push_back(PB);
+          OperandInfo.Infos.push_back(PB);
+        }
+      }
+      CmpOperands.clear();
+    }
+  }
+}
+
+// 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);
+    }
+  }
+  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);
+}
+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 split block.  For
+    // assume, we have to place it right before the assume to ensure we dominate
+    // all of our uses.
+    if (isa<PredicateBranch>(ValInfo)) {
+      auto *PBranch = cast<PredicateBranch>(ValInfo);
+      // It's possible we are trying to insert multiple predicateinfos in the
+      // same block at the beginning of the block.  When we do this, we need to
+      // insert them one after the other, not one before the other. To see if we
+      // have already inserted predicateinfo into this block, we see if Op !=
+      // OrigOp && Op->getParent() == PBranch->SplitBB.  Op must be an
+      // instruction we inserted if it's not the original op.
+      BasicBlock::iterator InsertPt;
+      if (Op == OrigOp ||
+          cast<Instruction>(Op)->getParent() != PBranch->SplitBB) {
+        InsertPt = PBranch->SplitBB->begin();
+        // Insert after last phi node.
+        while (isa<PHINode>(InsertPt))
+          ++InsertPt;
+      } else {
+        // Insert after op.
+        InsertPt = ++(cast<Instruction>(Op)->getIterator());
+      }
+      IRBuilder<> B(PBranch->SplitBB, InsertPt);
+      Function *IF = Intrinsic::getDeclaration(
+          F.getParent(), Intrinsic::predicateinfo, Op->getType());
+      Value *PIC = B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++));
+      PredicateMap.insert({PIC, ValInfo});
+      Result.Def = PIC;
+    } else {
+      auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
+      assert(PAssume &&
+             "Should not have gotten here without it being an assume");
+      // Unlike above, this should already insert in the right order when we
+      // insert multiple predicateinfos in the same block.  Because we are
+      // always inserting right before the assume (instead of the beginning of a
+      // block), newer insertions will end up after older ones.
+      IRBuilder<> B(PAssume->AssumeInst->getParent(),
+                    PAssume->AssumeInst->getIterator());
+      Function *IF = Intrinsic::getDeclaration(
+          F.getParent(), Intrinsic::predicateinfo, Op->getType());
+      Value *PIC = B.CreateCall(IF, Op);
+      PredicateMap.insert({PIC, ValInfo});
+      Result.Def = PIC;
+    }
+  }
+  return RenameStack.back().Def;
+}
+
+// Instead of the standard SSA renaming algorithm, which is O(Number of
+// instructions), and walks the entire dominator tree, we walk only the defs +
+// uses.  The standard SSA renaming algorithm does not really rely on the
+// dominator tree except to order the stack push/pops of the renaming stacks, so
+// that defs end up getting pushed before hitting the correct uses.  This does
+// not require the dominator tree, only the *order* of the dominator tree. The
+// complete and correct ordering of the defs and uses, in dominator tree is
+// contained in the DFS numbering of the dominator tree. So we sort the defs and
+// uses into the DFS ordering, and then just use the renaming stack as per
+// normal, pushing when we hit a def (which is a predicateinfo instruction),
+// popping when we are out of the dfs scope for that def, and replacing any uses
+// with top of stack if it exists.  In order to handle liveness without
+// propagating liveness info, we don't actually insert the predicateinfo
+// instruction def until we see a use that it would dominate.  Once we see such
+// a use, we materialize the predicateinfo instruction in the right place and
+// use it.
+//
+// TODO: Use this algorithm to perform fast single-variable renaming in
+// promotememtoreg and memoryssa.
+void PredicateInfo::renameUses(SmallPtrSetImpl<Value *> &OpsToRename) {
+  ValueDFS_Compare A(OBBMap);
+  // Compute liveness, and rename in O(uses) per Op.
+  for (auto *Op : OpsToRename) {
+    unsigned Counter = 0;
+    SmallVector<ValueDFS, 16> OrderedUses;
+    const auto &ValueInfo = getValueInfo(Op);
+    // Insert the possible copies into the def/use list.
+    // They will become real copies if we find a real use for them, and never
+    // created otherwise.
+    for (auto &PossibleCopy : ValueInfo.Infos) {
+      ValueDFS VD;
+      BasicBlock *CopyBB = nullptr;
+      // Determine where we are going to place the copy by the copy type.
+      // The predicate info for branches always come first, they will get
+      // materialized in the split block at the top of the block.
+      // The predicate info for assumes will be somewhere in the middle,
+      // it will get materialized in front of the assume.
+      if (const auto *PBranch = dyn_cast<PredicateBranch>(PossibleCopy)) {
+        CopyBB = PBranch->SplitBB;
+        VD.LocalNum = LN_First;
+      } else if (const auto *PAssume =
+                     dyn_cast<PredicateAssume>(PossibleCopy)) {
+        CopyBB = PAssume->AssumeInst->getParent();
+        VD.LocalNum = LN_Middle;
+      } else
+        llvm_unreachable("Unhandled predicate info type");
+      DomTreeNode *DomNode = DT.getNode(CopyBB);
+      if (!DomNode)
+        continue;
+      VD.DFSIn = DomNode->getDFSNumIn();
+      VD.DFSOut = DomNode->getDFSNumOut();
+      VD.PInfo = PossibleCopy;
+      OrderedUses.push_back(VD);
+    }
+
+    convertUsesToDFSOrdered(Op, OrderedUses);
+    std::sort(OrderedUses.begin(), OrderedUses.end(), A);
+    SmallVector<ValueDFS, 8> RenameStack;
+    // For each use, sorted into dfs order, push values and replaces uses with
+    // top of stack, which will represent the reaching def.
+    for (auto &VD : OrderedUses) {
+      // We currently do not materialize copy over copy, but we should decide if
+      // we want to.
+      bool PossibleCopy = VD.PInfo != nullptr;
+      if (RenameStack.empty()) {
+        DEBUG(dbgs() << "Rename Stack is empty\n");
+      } else {
+        DEBUG(dbgs() << "Rename Stack Top DFS numbers are ("
+                     << RenameStack.back().DFSIn << ","
+                     << RenameStack.back().DFSOut << ")\n");
+      }
+
+      DEBUG(dbgs() << "Current DFS numbers are (" << VD.DFSIn << ","
+                   << VD.DFSOut << ")\n");
+
+      bool ShouldPush = (VD.Def || PossibleCopy);
+      bool OutOfScope = !stackIsInScope(RenameStack, VD.DFSIn, VD.DFSOut);
+      if (OutOfScope || ShouldPush) {
+        // Sync to our current scope.
+        popStackUntilDFSScope(RenameStack, VD.DFSIn, VD.DFSOut);
+        ShouldPush |= (VD.Def || PossibleCopy);
+        if (ShouldPush) {
+          RenameStack.push_back(VD);
+        }
+      }
+      // If we get to this point, and the stack is empty we must have a use
+      // with no renaming needed, just skip it.
+      if (RenameStack.empty())
+        continue;
+      // Skip values, only want to rename the uses
+      if (VD.Def || PossibleCopy)
+        continue;
+      ValueDFS &Result = RenameStack.back();
+
+      // If the possible copy dominates something, materialize our stack up to
+      // this point. This ensures every comparison that affects our operation
+      // ends up with predicateinfo.
+      if (!Result.Def)
+        Result.Def = materializeStack(Counter, RenameStack, Op);
+
+      DEBUG(dbgs() << "Found replacement " << *Result.Def << " for "
+                   << *VD.Use->get() << " in " << *(VD.Use->getUser()) << "\n");
+      assert(DT.dominates(cast<Instruction>(Result.Def), *VD.Use) &&
+             "Predicateinfo def should have dominated this use");
+      VD.Use->set(Result.Def);
+    }
+  }
+}
+
+PredicateInfo::ValueInfo &PredicateInfo::getOrCreateValueInfo(Value *Operand) {
+  auto OIN = ValueInfoNums.find(Operand);
+  if (OIN == ValueInfoNums.end()) {
+    // This will grow it
+    ValueInfos.resize(ValueInfos.size() + 1);
+    // This will use the new size and give us a 0 based number of the info
+    auto InsertResult = ValueInfoNums.insert({Operand, ValueInfos.size() - 1});
+    assert(InsertResult.second && "Value info number already existed?");
+    return ValueInfos[InsertResult.first->second];
+  }
+  return ValueInfos[OIN->second];
+}
+
+const PredicateInfo::ValueInfo &
+PredicateInfo::getValueInfo(Value *Operand) const {
+  auto OINI = ValueInfoNums.lookup(Operand);
+  assert(OINI != 0 && "Operand was not really in the Value Info Numbers");
+  assert(OINI < ValueInfos.size() &&
+         "Value Info Number greater than size of Value Info Table");
+  return ValueInfos[OINI];
+}
+
+PredicateInfo::PredicateInfo(Function &F, DominatorTree &DT,
+                             AssumptionCache &AC)
+    : F(F), DT(DT), AC(AC) {
+  // Push an empty operand info so that we can detect 0 as not finding one
+  ValueInfos.resize(1);
+  buildPredicateInfo();
+}
+
+PredicateInfo::~PredicateInfo() {}
+
+void PredicateInfo::verifyPredicateInfo() const {}
+
+char PredicateInfoPrinterLegacyPass::ID = 0;
+
+PredicateInfoPrinterLegacyPass::PredicateInfoPrinterLegacyPass()
+    : FunctionPass(ID) {
+  initializePredicateInfoPrinterLegacyPassPass(
+      *PassRegistry::getPassRegistry());
+}
+
+void PredicateInfoPrinterLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  AU.addRequiredTransitive<DominatorTreeWrapperPass>();
+  AU.addRequired<AssumptionCacheTracker>();
+}
+
+bool PredicateInfoPrinterLegacyPass::runOnFunction(Function &F) {
+  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
+  auto PredInfo = make_unique<PredicateInfo>(F, DT, AC);
+  PredInfo->print(dbgs());
+  if (VerifyPredicateInfo)
+    PredInfo->verifyPredicateInfo();
+  return false;
+}
+
+PreservedAnalyses PredicateInfoPrinterPass::run(Function &F,
+                                                FunctionAnalysisManager &AM) {
+  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
+  auto &AC = AM.getResult<AssumptionAnalysis>(F);
+  OS << "PredicateInfo for function: " << F.getName() << "\n";
+  make_unique<PredicateInfo>(F, DT, AC)->print(OS);
+
+  return PreservedAnalyses::all();
+}
+
+/// \brief An assembly annotator class to print PredicateInfo information in
+/// comments.
+class PredicateInfoAnnotatedWriter : public AssemblyAnnotationWriter {
+  friend class PredicateInfo;
+  const PredicateInfo *PredInfo;
+
+public:
+  PredicateInfoAnnotatedWriter(const PredicateInfo *M) : PredInfo(M) {}
+
+  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))
+        OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge
+           << " Comparison:" << *PB->Comparison << " }\n";
+      else if (const auto *PA = dyn_cast<PredicateAssume>(PI))
+        OS << "; assume predicate info {"
+           << " Comparison:" << *PA->Comparison << " }\n";
+    }
+  }
+};
+
+void PredicateInfo::print(raw_ostream &OS) const {
+  PredicateInfoAnnotatedWriter Writer(this);
+  F.print(OS, &Writer);
+}
+
+void PredicateInfo::dump() const {
+  PredicateInfoAnnotatedWriter Writer(this);
+  F.print(dbgs(), &Writer);
+}
+
+PreservedAnalyses PredicateInfoVerifierPass::run(Function &F,
+                                                 FunctionAnalysisManager &AM) {
+  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
+  auto &AC = AM.getResult<AssumptionAnalysis>(F);
+  make_unique<PredicateInfo>(F, DT, AC)->verifyPredicateInfo();
+
+  return PreservedAnalyses::all();
+}
+}

lib/Transforms/Utils/Utils.cpp

void llvm::initializeTransformUtils(PassRegistry &Registry) {
   initializePromoteLegacyPassPass(Registry);
   initializeStripNonLineTableDebugInfoPass(Registry);
   initializeUnifyFunctionExitNodesPass(Registry);
   initializeInstSimplifierPass(Registry);
   initializeMetaRenamerPass(Registry);
   initializeMemorySSAWrapperPassPass(Registry);
   initializeMemorySSAPrinterLegacyPassPass(Registry);
   initializeStripGCRelocatesPass(Registry);
+  initializePredicateInfoPrinterLegacyPassPass(Registry);
 }
 
 /// LLVMInitializeTransformUtils - C binding for initializeTransformUtilsPasses.
 void LLVMInitializeTransformUtils(LLVMPassRegistryRef R) {
   initializeTransformUtils(*unwrap(R));
 }

test/Transforms/Util/PredicateInfo/condprop.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -print-predicateinfo -S | FileCheck %s
+
+@a = external global i32    ; <i32*> [#uses=7]
+
+define i32 @test1() nounwind {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 4
+; CHECK-NEXT:    br i1 [[TMP1]], label [[BB:%.*]], label [[BB1:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    br label [[BB8:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 5
+; CHECK-NEXT:    br i1 [[TMP3]], label [[BB2:%.*]], label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB8]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[TMP4:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 4
+; CHECK-NEXT:    br i1 [[TMP5]], label [[BB4:%.*]], label [[BB5:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    [[TMP6:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[TMP7:%.*]] = add i32 [[TMP6]], 5
+; CHECK-NEXT:    br label [[BB8]]
+; CHECK:       bb5:
+; CHECK-NEXT:    [[TMP8:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], 5
+; CHECK-NEXT:    br i1 [[TMP9]], label [[BB6:%.*]], label [[BB7:%.*]]
+; CHECK:       bb6:
+; CHECK-NEXT:    [[TMP10:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[TMP11:%.*]] = add i32 [[TMP10]], 4
+; CHECK-NEXT:    br label [[BB8]]
+; CHECK:       bb7:
+; CHECK-NEXT:    [[TMP12:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    br label [[BB8]]
+; CHECK:       bb8:
+; CHECK-NEXT:    [[DOT0:%.*]] = phi i32 [ [[TMP12]], [[BB7]] ], [ [[TMP11]], [[BB6]] ], [ [[TMP7]], [[BB4]] ], [ 4, [[BB2]] ], [ 5, [[BB]] ]
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i32 [[DOT0]]
+;
+entry:
+  %0 = load i32, i32* @a, align 4
+  %1 = icmp eq i32 %0, 4
+  br i1 %1, label %bb, label %bb1
+
+bb:   ; preds = %entry
+  br label %bb8
+
+bb1:    ; preds = %entry
+  %2 = load i32, i32* @a, align 4
+  %3 = icmp eq i32 %2, 5
+  br i1 %3, label %bb2, label %bb3
+
+bb2:    ; preds = %bb1
+  br label %bb8
+
+bb3:    ; preds = %bb1
+  %4 = load i32, i32* @a, align 4
+  %5 = icmp eq i32 %4, 4
+  br i1 %5, label %bb4, label %bb5
+
+bb4:    ; preds = %bb3
+  %6 = load i32, i32* @a, align 4
+  %7 = add i32 %6, 5
+  br label %bb8
+
+bb5:    ; preds = %bb3
+  %8 = load i32, i32* @a, align 4
+  %9 = icmp eq i32 %8, 5
+  br i1 %9, label %bb6, label %bb7
+
+bb6:    ; preds = %bb5
+  %10 = load i32, i32* @a, align 4
+  %11 = add i32 %10, 4
+  br label %bb8
+
+bb7:    ; preds = %bb5
+  %12 = load i32, i32* @a, align 4
+  br label %bb8
+
+bb8:    ; preds = %bb7, %bb6, %bb4, %bb2, %bb
+  %.0 = phi i32 [ %12, %bb7 ], [ %11, %bb6 ], [ %7, %bb4 ], [ 4, %bb2 ], [ 5, %bb ]
+  br label %return
+
+return:   ; preds = %bb8
+  ret i32 %.0
+}
+
+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:    [[Y_0:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[Y]])
+; CHECK-NEXT:    [[YZ_0:%.*]] = call i1 @llvm.predicateinfo.i1(i1 [[YZ]])
+; CHECK-NEXT:    [[X_0:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[X]])
+; CHECK-NEXT:    [[XZ_0:%.*]] = call i1 @llvm.predicateinfo.i1(i1 [[XZ]])
+; CHECK-NEXT:    call void @foo(i1 [[XZ_0]])
+; CHECK-NEXT:    call void @foo(i1 [[YZ_0]])
+; CHECK-NEXT:    call void @bar(i32 [[X_0]])
+; CHECK-NEXT:    call void @bar(i32 [[Y_0]])
+; CHECK-NEXT:    ret void
+; CHECK:       nope:
+; CHECK-NEXT:    call void @foo(i1 [[Z]])
+; 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)
+  call void @foo(i1 %yz)
+  call void @bar(i32 %x)
+  call void @bar(i32 %y)
+  ret void
+nope:
+  call void @foo(i1 %z)
+  ret void
+}
+
+; CHECK-LABEL: @test4(
+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 [[X]])
+; 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:    [[Y_0:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[Y]])
+; CHECK-NEXT:    [[X_0:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[X]])
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[X_0]], [[Y_0]]
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       different:
+; CHECK-NEXT:    [[Y_1:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[Y]])
+; CHECK-NEXT:    [[X_1:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[X]])
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp eq i32 [[X_1]], [[Y_1]]
+; CHECK-NEXT:    ret i1 [[CMP3]]
+;
+  %cmp = icmp eq i32 %x, %y
+  br i1 %cmp, label %same, label %different
+
+same:
+  %cmp2 = icmp ne i32 %x, %y
+  ret i1 %cmp2
+
+different:
+  %cmp3 = icmp eq i32 %x, %y
+  ret i1 %cmp3
+}
+
+; CHECK-LABEL: @test6(
+define i1 @test6(i32 %x, i32 %y) {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp eq i32 [[X]], [[Y]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
+; CHECK:       same:
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       different:
+; CHECK-NEXT:    ret i1 [[CMP3]]
+;
+  %cmp2 = icmp ne i32 %x, %y
+  %cmp = icmp eq i32 %x, %y
+  %cmp3 = icmp eq i32 %x, %y
+  br i1 %cmp, label %same, label %different
+
+same:
+  ret i1 %cmp2
+
+different:
+  ret i1 %cmp3
+}
+
+; CHECK-LABEL: @test6_fp(
+define i1 @test6_fp(float %x, float %y) {
+; CHECK-LABEL: @test6_fp(
+; CHECK-NEXT:    [[CMP2:%.*]] = fcmp une float [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = fcmp oeq float [[X]], [[Y]]
+; CHECK-NEXT:    [[CMP3:%.*]] = fcmp oeq float [[X]], [[Y]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
+; CHECK:       same:
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       different:
+; CHECK-NEXT:    ret i1 [[CMP3]]
+;
+  %cmp2 = fcmp une float %x, %y
+  %cmp = fcmp oeq float %x, %y
+  %cmp3 = fcmp oeq float  %x, %y
+  br i1 %cmp, label %same, label %different
+
+same:
+  ret i1 %cmp2
+
+different:
+  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:    [[Y_0:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[Y]])
+; CHECK-NEXT:    [[X_0:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[X]])
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 [[X_0]], [[Y_0]]
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       different:
+; CHECK-NEXT:    [[Y_1:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[Y]])
+; CHECK-NEXT:    [[X_1:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[X]])
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp sgt i32 [[X_1]], [[Y_1]]
+; CHECK-NEXT:    ret i1 [[CMP3]]
+;
+  %cmp = icmp sgt i32 %x, %y
+  br i1 %cmp, label %same, label %different
+
+same:
+  %cmp2 = icmp sle i32 %x, %y
+  ret i1 %cmp2
+
+different:
+  %cmp3 = icmp sgt i32 %x, %y
+  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:    [[Y_0:%.*]] = call float @llvm.predicateinfo.f32(float [[Y]])
+; CHECK-NEXT:    [[X_0:%.*]] = call float @llvm.predicateinfo.f32(float [[X]])
+; CHECK-NEXT:    [[CMP2:%.*]] = fcmp ule float [[X_0]], [[Y_0]]
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       different:
+; CHECK-NEXT:    [[Y_1:%.*]] = call float @llvm.predicateinfo.f32(float [[Y]])
+; CHECK-NEXT:    [[X_1:%.*]] = call float @llvm.predicateinfo.f32(float [[X]])
+; CHECK-NEXT:    [[CMP3:%.*]] = fcmp ogt float [[X_1]], [[Y_1]]
+; CHECK-NEXT:    ret i1 [[CMP3]]
+;
+  %cmp = fcmp ogt float %x, %y
+  br i1 %cmp, label %same, label %different
+
+same:
+  %cmp2 = fcmp ule float %x, %y
+  ret i1 %cmp2
+
+different:
+  %cmp3 = fcmp ogt float %x, %y
+  ret i1 %cmp3
+}
+
+; CHECK-LABEL: @test8(
+define i1 @test8(i32 %x, i32 %y) {
+; CHECK-LABEL: @test8(
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp sgt i32 [[X]], [[Y]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
+; CHECK:       same:
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       different:
+; CHECK-NEXT:    ret i1 [[CMP3]]
+;
+  %cmp2 = icmp sle i32 %x, %y
+  %cmp = icmp sgt i32 %x, %y
+  %cmp3 = icmp sgt i32 %x, %y
+  br i1 %cmp, label %same, label %different
+
+same:
+  ret i1 %cmp2
+
+different:
+  ret i1 %cmp3
+}
+
+; CHECK-LABEL: @test8_fp(
+define i1 @test8_fp(float %x, float %y) {
+; CHECK-LABEL: @test8_fp(
+; CHECK-NEXT:    [[CMP2:%.*]] = fcmp ule float [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = fcmp ogt float [[X]], [[Y]]
+; CHECK-NEXT:    [[CMP3:%.*]] = fcmp ogt float [[X]], [[Y]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
+; CHECK:       same:
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       different:
+; CHECK-NEXT:    ret i1 [[CMP3]]
+;
+  %cmp2 = fcmp ule float %x, %y
+  %cmp = fcmp ogt float %x, %y
+  %cmp3 = fcmp ogt float %x, %y
+  br i1 %cmp, label %same, label %different
+
+same:
+  ret i1 %cmp2
+
+different:
+  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:    [[J_0:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[J]])
+; CHECK-NEXT:    [[I_0:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[I]])
+; CHECK-NEXT:    [[DIFF:%.*]] = sub i32 [[I_0]], [[J_0]]
+; CHECK-NEXT:    ret i32 [[DIFF]]
+; 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
+
+ret:
+  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:    [[J_0:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[J]])
+; CHECK-NEXT:    [[I_0:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[I]])
+; CHECK-NEXT:    [[DIFF:%.*]] = sub i32 [[I_0]], [[J_0]]
+; CHECK-NEXT:    ret i32 [[DIFF]]
+; 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
+
+ret:
+  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:    [[V1_0:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[V1]])
+; CHECK-NEXT:    ret i32 [[V1_0]]
+; CHECK:       next:
+; CHECK-NEXT:    [[V0_0:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[V0]])
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[X:%.*]], [[V0_0]]
+; CHECK-NEXT:    br i1 [[CMP2]], label [[COND_TRUE2:%.*]], label [[NEXT2:%.*]]
+; CHECK:       cond_true2:
+; CHECK-NEXT:    [[V0_0_1:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[V0_0]])
+; CHECK-NEXT:    ret i32 [[V0_0_1]]
+; 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
+
+next:
+  %cmp2 = icmp eq i32 %x, %v0
+  br i1 %cmp2, label %cond_true2, label %next2
+
+cond_true2:
+  ret i32 %v0
+
+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 [ [[X]], [[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 ]
+  ret i32 %res
+}

test/Transforms/Util/PredicateInfo/testand.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -print-predicateinfo -analyze < %s 2>&1 | FileCheck %s
+
+declare void @foo(i1)
+declare void @bar(i32)
+declare void @llvm.assume(i1)
+
+define void @testand(i32 %x, i32 %y) {
+; CHECK-LABEL: @testand(
+; 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:%.*]], label [[NOPE:%.*]]
+; CHECK:       both:
+; CHECK:         [[Y_0:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[Y]])
+; CHECK:         [[YZ_0:%.*]] = call i1 @llvm.predicateinfo.i1(i1 [[YZ]])
+; CHECK:         [[X_0:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[X]])
+; CHECK:         [[XZ_0:%.*]] = call i1 @llvm.predicateinfo.i1(i1 [[XZ]])
+; CHECK-NEXT:    call void @foo(i1 [[XZ_0]])
+; CHECK-NEXT:    call void @foo(i1 [[YZ_0]])
+; CHECK-NEXT:    call void @bar(i32 [[X_0]])
+; CHECK-NEXT:    call void @bar(i32 [[Y_0]])
+; CHECK-NEXT:    ret void
+; CHECK:       nope:
+; CHECK-NEXT:    call void @foo(i1 [[Z]])
+; 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, label %nope
+both:
+  call void @foo(i1 %xz)
+  call void @foo(i1 %yz)
+  call void @bar(i32 %x)
+  call void @bar(i32 %y)
+  ret void
+nope:
+  call void @foo(i1 %z)
+  ret void
+}
+define void @testandsame(i32 %x, i32 %y) {
+; CHECK-LABEL: @testandsame(
+; CHECK-NEXT:    [[XGT:%.*]] = icmp sgt i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[XLT:%.*]] = icmp slt i32 [[X]], 100
+; CHECK-NEXT:    [[Z:%.*]] = and i1 [[XGT]], [[XLT]]
+; CHECK-NEXT:    br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]]
+; CHECK:       both:
+; CHECK:         [[XLT_0:%.*]] = call i1 @llvm.predicateinfo.i1(i1 [[XLT]])
+; CHECK:         [[X_0:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[X]])
+; CHECK:         [[X_0_1:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[X_0]])
+; CHECK:         [[XGT_0:%.*]] = call i1 @llvm.predicateinfo.i1(i1 [[XGT]])
+; CHECK-NEXT:    call void @foo(i1 [[XGT_0]])
+; CHECK-NEXT:    call void @foo(i1 [[XLT_0]])
+; CHECK-NEXT:    call void @bar(i32 [[X_0_1]])
+; CHECK-NEXT:    ret void
+; CHECK:       nope:
+; CHECK-NEXT:    call void @foo(i1 [[Z]])
+; CHECK-NEXT:    ret void
+;
+  %xgt = icmp sgt i32 %x, 0
+  %xlt = icmp slt i32 %x, 100
+  %z = and i1 %xgt, %xlt
+  br i1 %z, label %both, label %nope
+both:
+  call void @foo(i1 %xgt)
+  call void @foo(i1 %xlt)
+  call void @bar(i32 %x)
+  ret void
+nope:
+  call void @foo(i1 %z)
+  ret void
+}
+
+
+
+
+define void @testandassume(i32 %x, i32 %y) {
+; CHECK-LABEL: @testandassume(
+; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
+; CHECK-NEXT:    [[Z:%.*]] = and i1 [[XZ]], [[YZ]]
+; CHECK:         [[TMP1:%.*]] = call i1 @llvm.predicateinfo.i1(i1 [[XZ]])
+; CHECK:         [[TMP2:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[X]])
+; CHECK:         [[TMP3:%.*]] = call i1 @llvm.predicateinfo.i1(i1 [[YZ]])
+; CHECK:         [[TMP4:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[Y]])
+; CHECK-NEXT:    call void @llvm.assume(i1 [[Z]])
+; CHECK-NEXT:    br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]]
+; CHECK:       both:
+; CHECK:         [[DOT03:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[TMP4]])
+; CHECK:         [[DOT02:%.*]] = call i1 @llvm.predicateinfo.i1(i1 [[TMP3]])
+; CHECK:         [[DOT01:%.*]] = call i32 @llvm.predicateinfo.i32(i32 [[TMP2]])
+; CHECK:         [[DOT0:%.*]] = call i1 @llvm.predicateinfo.i1(i1 [[TMP1]])
+; CHECK-NEXT:    call void @foo(i1 [[DOT0]])
+; CHECK-NEXT:    call void @foo(i1 [[DOT02]])
+; CHECK-NEXT:    call void @bar(i32 [[DOT01]])
+; CHECK-NEXT:    call void @bar(i32 [[DOT03]])
+; CHECK-NEXT:    ret void
+; CHECK:       nope:
+; CHECK-NEXT:    call void @foo(i1 [[Z]])
+; CHECK-NEXT:    ret void
+;
+  %xz = icmp eq i32 %x, 0
+  %yz = icmp eq i32 %y, 0
+  %z = and i1 %xz, %yz
+  call void @llvm.assume(i1 %z)
+  br i1 %z, label %both, label %nope
+both:
+  call void @foo(i1 %xz)
+  call void @foo(i1 %yz)
+  call void @bar(i32 %x)
+  call void @bar(i32 %y)
+  ret void
+nope:
+  call void @foo(i1 %z)
+  ret void
+}