[PredicateInfo] Add additional RenamedOp field to PB.

[fhahn]

Summary

OriginalOp of a predicate always refers to the original IR
value that was renamed. So for nested predicates of the same value, it
will always refer to the original IR value.

For the use in SCCP however, we need to find the renamed value that is
currently used in the condition associated with the predicate. This
patch adds a new RenamedOp field to do exactly that.

NewGVN currently relies on the existing behavior to merge instruction
metadata. A test case to check for exactly that has been added in
195fa4bfae10.

[fhahn]

Update to add option to set OriginalOp to the renamed value it refers to. I will update the description shortly.

[fhahn]

Rebase and add new option the PredicateInfo to configure renaming behavior.

[nikic]

Do we need to have this behind an option? That is, are there any PredicateInfo consumers who would not want this behavior?

[fhahn]

In D78133#2131838, @nikic wrote:

Do we need to have this behind an option? That is, are there any PredicateInfo consumers who would not want this behavior?

Currently NewGVN relies on the current behavior. It uses it to easily look up the original instruction and uses it to merge the metadata of replacement instructions (which is not an issue for SCCP because we don't replace the predicates with other equivalent instructions which could have metadata). I guess we could try to keep track of the original instruction in NewGVN (or traverse the chain there), but I don't think it's worth blocking the patch on the change to NewGVN.

[nikic]

In D78133#2134287, @fhahn wrote:

In D78133#2131838, @nikic wrote:

Do we need to have this behind an option? That is, are there any PredicateInfo consumers who would not want this behavior?

Currently NewGVN relies on the current behavior. It uses it to easily look up the original instruction and uses it to merge the metadata of replacement instructions (which is not an issue for SCCP because we don't replace the predicates with other equivalent instructions which could have metadata). I guess we could try to keep track of the original instruction in NewGVN (or traverse the chain there), but I don't think it's worth blocking the patch on the change to NewGVN.

Why don't we include both variants? While NewGVN needs the current OriginalOp for the replacement instruction patching, it also needs what is being implemented here (lets call it CondOp) when originally handling the PredicateInfo. As this comment indicates, NewGVN currently has the same problem as SCCP: https://github.com/llvm/llvm-project/blob/2279380eab08219911910e1ecdcef3eacb0b7f0c/llvm/lib/Transforms/Scalar/NewGVN.cpp#L1565-L1572

As PredicateInfo structures aren't particularly memory critical, I'd suggest to include both OriginalOp (value prior to any renaming) and CondOp (value used inside the condition) and use them as appropriate.

[fhahn]

Add new RenamedOp to PredicateBase instead of having a separate option.

In D78133#2131838, @nikic wrote:

Why don't we include both variants? While NewGVN needs the current OriginalOp for the replacement instruction patching, it also needs what is being implemented here (lets call it CondOp) when originally handling the PredicateInfo. As this comment indicates, NewGVN currently has the same problem as SCCP: https://github.com/llvm/llvm-project/blob/2279380eab08219911910e1ecdcef3eacb0b7f0c/llvm/lib/Transforms/Scalar/NewGVN.cpp#L1565-L1572

As PredicateInfo structures aren't particularly memory critical, I'd suggest to include both OriginalOp (value prior to any renaming) and CondOp (value used inside the condition) and use them as appropriate.

Initially I wanted to not increase memory consumption, but it's probably not a big deal. I also had same patches further reducing the memory consumption here, but did not have time to follow up on them. Anyways, I've added a separate RenamedOp field.

[nikic]

LG

[nikic]

I've added a test case in https://github.com/llvm/llvm-project/commit/a0b549602612fa2577068bcdcae3bfbc6c9c3264, which shows a case where the RenamedOp doesn't work quite right. In this case RenamedOp should always refer back to %cmp or %x, but ends up refering to %cmp.0, %x.0 and %x.0.1. I don't think this matters in a practical way though, because we don't get any additional information from the dominated predicate infos. It still seems like we either shouldn't place those predicate infos (because they're redundant), or provide them with a correct RenamedOp though.

[nikic]

Okay, after thinking about this a bit more, this does impact analysis quality. Here is a better test case:

define i32 @test2(i32 %x) {
entry:
  %cmp1 = icmp sgt i32 %x, 0
  %cmp2 = icmp sgt i32 %x, 10
  br i1 %cmp1, label %bb2, label %exit1

bb2:
  br i1 %cmp2, label %exit2, label %exit3

exit1:
  ret i32 0

exit2:
  ret i32 %x

exit3:
  ret i32 %x
}

Gives us:

define i32 @test2(i32 %x) {
entry:
  %cmp1 = icmp sgt i32 %x, 0
  %cmp2 = icmp sgt i32 %x, 10
; Has predicate info
; branch predicate info { TrueEdge: 1 Comparison:  %cmp1 = icmp sgt i32 %x, 0 Edge: [label %entry,label %bb2], RenamedOp: %x }
  %x.0 = call i32 @llvm.ssa.copy.94226533345936(i32 %x)
  br i1 %cmp1, label %bb2, label %exit1

bb2:                                              ; preds = %entry
; Has predicate info
; branch predicate info { TrueEdge: 1 Comparison:  %cmp2 = icmp sgt i32 %x, 10 Edge: [label %bb2,label %exit2], RenamedOp: %x }
  %x.0.1 = call i32 @llvm.ssa.copy.94226533345936(i32 %x.0)
; Has predicate info
; branch predicate info { TrueEdge: 0 Comparison:  %cmp2 = icmp sgt i32 %x, 10 Edge: [label %bb2,label %exit3], RenamedOp: %x.0 }
  %x.0.2 = call i32 @llvm.ssa.copy.94226533345936(i32 %x.0)
  br i1 %cmp2, label %exit2, label %exit3

exit1:                                            ; preds = %entry
  ret i32 0

exit2:                                            ; preds = %bb2
  ret i32 %x.0.1

exit3:                                            ; preds = %bb2
  ret i32 %x.0.2
}

Note that the false edge has RenamedOp: %x.0, but the comparison uses %x. That means we're going to lose the additional bound.

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

 // All of our predicate information has at least a comparison.
 class PredicateBase : public ilist_node<PredicateBase> {
 public:
   PredicateType Type;
   // The original operand before we renamed it.
   // This can be use by passes, when destroying predicateinfo, to know
   // whether they can just drop the intrinsic, or have to merge metadata.
   Value *OriginalOp;
+  // The renamed operand in the condition used for this predicate. For nested
+  // predicates, this is different to OriginalOp which refers to the initial
+  // operand.
+  Value *RenamedOp;
   PredicateBase(const PredicateBase &) = delete;
   PredicateBase &operator=(const PredicateBase &) = delete;
   PredicateBase() = delete;
   virtual ~PredicateBase() = default;
 
 protected:
   PredicateBase(PredicateType PT, Value *Op) : Type(PT), OriginalOp(Op) {}
 };

llvm/lib/Transforms/Utils/PredicateInfo.cpp

Value *PredicateInfoBuilder::materializeStack(unsigned int &Counter,
   // 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;
+    ValInfo->RenamedOp = (RenameStack.end() - Start) == RenameStack.begin()
+                             ? OrigOp
+                             : (RenameStack.end() - Start - 1)->Def;
     // For edge predicates, we can just place the operand in the block before
     // the terminator.  For assume, we have to place it right before the assume
     // to ensure we dominate all of our uses.  Always insert right before the
     // relevant instruction (terminator, assume), so that we insert in proper
     // order in the case of multiple predicateinfo in the same block.
     if (isa<PredicateWithEdge>(ValInfo)) {
       IRBuilder<> B(getBranchTerminator(ValInfo));
       Function *IF = getCopyDeclaration(F.getParent(), Op->getType());