[ConstraintElimination] Add function arguments to constraint system before solving

[zjaffal]

Summary

If there is an optimisation opportunity and the function argument hasn’t been added to constraint
system through previous facts we fail to optimise it.

It might be a good idea to start the constraint system with all the function arguments added to the system

[zjaffal]

Seperate the patch from depending on other ConstraintElimination patches

[fhahn]

llvm/include/llvm/Analysis/ConstraintSystem.h

16

Not needed?

21–22

Is Argument used?Maybe FunctionArgs should use Argument * instead of Value *

22

keep newline here.

70

This passes the full vector by value. Use ArrayRef<Value *> instead.

78

Initialise this like Value2Index, as in : Value2Index(Value2Index), NumVariables(Value2Index.size())`.

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

143

Initialise UnsignedCS and SignedCS like DL, as in : UnsignedCS(FunctionArgs), SignedCS(FunctionArgs), DL(DL)

[zjaffal]

1. Pass FunctionArgs as ArrayRef<Value *> to ConstraintInfo and ConstraintSystem
2. Remove unecessary import
3. Change variable initialization for ConstraintInfo and ConstraintSystem

[fhahn]

LGTM, thanks!

llvm/include/llvm/Analysis/ConstraintSystem.h

22

unrelated change, can you undo this before committing?

llvm/include/llvm/Analysis/ConstraintSystem.h

 //===- ConstraintSystem.h -  A system of linear constraints. --------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
 #define LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
 
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 
 #include <string>
 
 namespace llvm {
 
 class Value;
-
 class ConstraintSystem {
   struct Entry {
     int64_t Coefficient;
     uint16_t Id;
 
     Entry(int64_t Coefficient, uint16_t Id)
         : Coefficient(Coefficient), Id(Id) {}
   };
 
class ConstraintSystem {
   /// Returns true if there may be a solution for the constraints in the system.
   bool mayHaveSolutionImpl();
 
   /// Get list of variable names from the Value2Index map.
   SmallVector<std::string> getVarNamesList() const;
 
 public:
   ConstraintSystem() {}
+  ConstraintSystem(ArrayRef<Value *> FunctionArgs) {
+    NumVariables += FunctionArgs.size();
+    for (auto *Arg : FunctionArgs) {
+      Value2Index.insert({Arg, Value2Index.size() + 1});
+    }
+  }
   ConstraintSystem(const DenseMap<Value *, unsigned> &Value2Index)
-      : Value2Index(Value2Index) {}
+      : NumVariables(Value2Index.size()), Value2Index(Value2Index) {}
 
   bool addVariableRow(ArrayRef<int64_t> R) {
     assert(Constraints.empty() || R.size() == NumVariables);
     // If all variable coefficients are 0, the constraint does not provide any
     // usable information.
     if (all_of(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
       return false;
 
     SmallVector<Entry, 4> NewRow;

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

 class ConstraintInfo {
 
   ConstraintSystem UnsignedCS;
   ConstraintSystem SignedCS;
 
   const DataLayout &DL;
 
 public:
-  ConstraintInfo(const DataLayout &DL) : DL(DL) {}
+  ConstraintInfo(const DataLayout &DL, ArrayRef<Value *> FunctionArgs)
+      : UnsignedCS(FunctionArgs), SignedCS(FunctionArgs), DL(DL) {}
 
   DenseMap<Value *, unsigned> &getValue2Index(bool Signed) {
     return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index();
   }
   const DenseMap<Value *, unsigned> &getValue2Index(bool Signed) const {
     return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index();
   }
 
tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info,
   }
   return Changed;
 }
 
 static bool eliminateConstraints(Function &F, DominatorTree &DT,
                                  OptimizationRemarkEmitter &ORE) {
   bool Changed = false;
   DT.updateDFSNumbers();
-
-  ConstraintInfo Info(F.getParent()->getDataLayout());
+  SmallVector<Value *> FunctionArgs;
+  for (Value &Arg : F.args())
+    FunctionArgs.push_back(&Arg);
+  ConstraintInfo Info(F.getParent()->getDataLayout(), FunctionArgs);
   State S(DT);
   std::unique_ptr<Module> ReproducerModule(
       DumpReproducers ? new Module(F.getName(), F.getContext()) : nullptr);
 
   // First, collect conditions implied by branches and blocks with their
   // Dominator DFS in and out numbers.
   for (BasicBlock &BB : F) {
     if (!DT.getNode(&BB))

llvm/test/Transforms/ConstraintElimination/transfer-signed-facts-to-unsigned.ll

 
 then:
   ret i1 0
 
 else:
   ret i1 1
 }
 
-; TODO: Even though %cnt is not known signed positive %cmp can be simplified
-; because %add.ptr uses it zero-extended.
 define i1 @cnt_not_known_positive_sgt_against_base_with_zext(ptr %p, i32 %cnt) {
 ; CHECK-LABEL: @cnt_not_known_positive_sgt_against_base_with_zext(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[CNT:%.*]], -2
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
 ; CHECK-NEXT:    [[EXT:%.*]] = zext i32 [[CNT]] to i64
 ; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 [[EXT]]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp uge ptr [[ADD_PTR]], [[P]]
-; CHECK-NEXT:    br i1 [[CMP_1]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK-NEXT:    br i1 true, label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       else:
 ; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %cmp = icmp sgt i32 %cnt, -2
   tail call void @llvm.assume(i1 %cmp)
   %ext = zext i32 %cnt to i64
   %add.ptr = getelementptr inbounds i32, ptr %p, i64 %ext
   %cmp.1 = icmp uge ptr %add.ptr, %p
   br i1 %cmp.1, label %then, label %else
 
 then:
   ret i1 0
 
 else:
   ret i1 1
 }
 
-; TODO: Even though %cnt is not known signed positive %cmp can be simplified
-; because %add.ptr uses it zero-extended.
 define i1 @cnt_not_known_positive_sge_against_base_with_zext(ptr %p, i32 %cnt) {
 ; CHECK-LABEL: @cnt_not_known_positive_sge_against_base_with_zext(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i32 [[CNT:%.*]], -1
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
 ; CHECK-NEXT:    [[EXT:%.*]] = zext i32 [[CNT]] to i64
 ; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 [[EXT]]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp uge ptr [[ADD_PTR]], [[P]]
-; CHECK-NEXT:    br i1 [[CMP_1]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK-NEXT:    br i1 true, label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       else:
 ; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %cmp = icmp sge i32 %cnt, -1
   tail call void @llvm.assume(i1 %cmp)

 then:
   ret i1 0
 
 else:
   tail call void @sink(ptr nonnull %p)
   ret i1 1
 }
 
-; TODO: Even though %cnt is not known signed positive %cmp can be simplified
 ; because %add.ptr uses it zero-extended.
 define i1 @cnt_not_known_positive_from_branch_check_against_base_struct_ugt_with_zext(ptr %p, i32 %cnt) {
 ; CHECK-LABEL: @cnt_not_known_positive_from_branch_check_against_base_struct_ugt_with_zext(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[CNT:%.*]], -2
 ; CHECK-NEXT:    br i1 [[CMP]], label [[CHECK:%.*]], label [[ELSE:%.*]]
 ; CHECK:       check:
 ; CHECK-NEXT:    [[EXT:%.*]] = zext i32 [[CNT]] to i64
 ; CHECK-NEXT:    [[GEP_EXT:%.*]] = getelementptr inbounds [[T:%.*]], ptr [[P:%.*]], i64 0, i32 1, i64 [[EXT]]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ugt ptr [[GEP_EXT]], [[P]]
-; CHECK-NEXT:    br i1 [[CMP_1]], label [[THEN:%.*]], label [[ELSE]]
+; CHECK-NEXT:    br i1 true, label [[THEN:%.*]], label [[ELSE]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       else:
 ; CHECK-NEXT:    tail call void @sink(ptr nonnull [[P]])
 ; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %cmp = icmp sgt i32 %cnt, -2