[SCCP] Add initial support for propagation through freeze.

[fhahn]

Summary

This patch implements initial support for freeze instructions in
[IP]SCCP.

If the operand is known to be undef, exit early and wait until it
changes. If it stays undef until the end of solving, resolvedUndefsIn
will take care of handling it. At the moment, it will be marked as
overdefined.

Otherwise just merge in the value of the operand.

[nikic]

What about constant lattice element with a constant expression that may be undef/poison? What about constantrange_including_undef lattice element?

[fhahn]

In D124327#3469848, @nikic wrote:

What about constant lattice element with a constant expression that may be undef/poison? What about constantrange_including_undef lattice element?

I *think* the handling in the patch should be conservatively correct, as the it should be a valid over-approximation to have the freeze result may include undef.

If we use the range to replace with a constant, the assumption is that we choose a value in the range and which particular one doesn't matter. As users of the range have to assume the value could be any in the range, I don't think we can get in a situation where 2 different users would pick different values due to undef in the range. This should effectively delay committing to a constant value for the freeze until we use the range to replace with a constant. The _including_undef part of the name is probably not entirely accurate. The important property is that we cannot use such ranges to perform simplifications *without* replacing the value with a constant ( (see test case`@test1_sext_op_can_be_undef_but_frozen` in rGb2a885a290be)

If we would need to commit to eliminating the undef part of a range at the point we mark the result of the freeze we would have to mark it as overdefined.

[nikic]

I tested this patch, and it folds

@g = external global i8

define i64 @test() {
  %x = freeze i64 add nuw (i64 ptrtoint (ptr @g to i64), i64 1)
  ret i64 %x
}

to

@g = external global i8

define i64 @test() {
  ret i64 add nuw (i64 ptrtoint (ptr @g to i64), i64 1)
}

which is clearly not right due to the presence of the nuw flag. This needs an isGuaranteedNotToBeUndefOrPoison check for the constant value.

[nikic]

llvm/test/Transforms/SCCP/freeze.ll

48

Let's assume %x is poison here, then %and is poison and %and.fr can take any value, while you assume that it must be in [0,3].

Here's an example of how this goes wrong across multiple passes:

declare void @use(i64) 
 
define internal i1 @test(i64 %a) {
  %b = or i64 %a, 2 
  %x = freeze i64 %b
  call void @use(i64 %x) 
  %c = icmp eq i64 %x, 0 
  ret i1 %c
} 
 
define i1 @test2() {
  %c = call i1 @test(i64 poison)
  ret i1 %c
}

; opt -S -sccp -inline -instcombine

define i1 @test2() {
  call void @use(i64 0)
  ret i1 false
}

As you can see, we both claim that %x != 0 and pass %x == 0 to @use(). This example uses -sccp to make sure SCCP doesn't have a global view.

llvm/lib/Transforms/Utils/SCCPSolver.cpp

private:
 
   void visitCallBase(CallBase &CB);
   void visitResumeInst(ResumeInst &I) { /*returns void*/
   }
   void visitUnreachableInst(UnreachableInst &I) { /*returns void*/
   }
   void visitFenceInst(FenceInst &I) { /*returns void*/
   }
+  void visitFreezeInst(FreezeInst &I) {
+    auto &OpV = getValueState(I.getOperand(0));
+    // If the operand is known to be undef, wait until it changes. If it stays
+    // undef until the end of solving, resolvedUndefsIn will handle it.
+    if (OpV.isUndef())
+      return;
+
+    auto &LV = getValueState(&I);
+    mergeInValue(LV, &I, OpV);
+  }
 
   void visitInstruction(Instruction &I);
 
 public:
   void addAnalysis(Function &F, AnalysisResultsForFn A) {
     AnalysisResults.insert({&F, std::move(A)});
   }
 

llvm/test/Transforms/SCCP/freeze.ll

;
   %fr = freeze <2 x i32> undef
   ret <2 x i32> %fr
 }
 
 define i1 @propagate_range_from_and_through_freeze(i32 %x, i32 %y) {
 ; CHECK-LABEL: @propagate_range_from_and_through_freeze(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 3
 ; CHECK-NEXT:    [[AND_FR:%.*]] = freeze i32 [[AND]]
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i32 [[AND_FR]], 100
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ule i32 [[AND_FR]], 3
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
-; CHECK-NEXT:    [[F_2:%.*]] = icmp ugt i32 [[AND_FR]], 3
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i32 [[AND_FR]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
-; CHECK-NEXT:    [[R_1:%.*]] = xor i1 [[T_1]], [[F_1]]
-; CHECK-NEXT:    [[R_2:%.*]] = xor i1 [[R_1]], [[F_2]]
-; CHECK-NEXT:    [[R_3:%.*]] = xor i1 [[R_2]], [[C_1]]
+; CHECK-NEXT:    [[R_3:%.*]] = xor i1 true, [[C_1]]
 ; CHECK-NEXT:    ret i1 [[R_3]]
 ;
   %and = and i32 %x, 3
   %and.fr = freeze i32 %and
   %f.1 = icmp eq i32 %and.fr, 100
   call void @use(i1 %f.1)
   %t.1 = icmp ule i32 %and.fr, 3
   call void @use(i1 %t.1)

 ; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[TRUE_2:%.*]], label [[EXIT:%.*]]
 ; CHECK:       true.2:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       false:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 10, [[TRUE_1]] ], [ 20, [[TRUE_2]] ], [ undef, [[FALSE]] ]
 ; CHECK-NEXT:    [[P_FR:%.*]] = freeze i32 [[P]]
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ule i32 [[P_FR]], 20
-; CHECK-NEXT:    [[T_2:%.*]] = icmp uge i32 [[P_FR]], 10
-; CHECK-NEXT:    [[RES:%.*]] = xor i1 [[T_1]], [[T_2]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 false
 ;
   br i1 %c.1, label %true.1, label %false
 
 true.1:
   br i1 %c.2, label %true.2, label %exit
 
 true.2:
   br label %exit