[SCCP] Replace structs with constants if all the lattice values are constant

[davide]

Summary

I originally started working on adding support for vectors insertelement and friends than I realized we could re-use the code we use for handling structs for the purpose.
So, I decided to struct support first and put the rewrite of http://reviews.llvm.org/D22186 on hold.
This patch only works for SCCP but it shouldn't be hard to port to the interprocedural version of this pass if we agree this is the right way of handling this case.

[eli.friedman]

You probably want to refactor this if you're planning to use it from IPSCCP... but you can do that in the followup, I guess.

In terms of expanding the struct code for vectors, I guess that might work? It's probably a lot of work for not much benefit, though; it would involve touching every single operation which can work on vectors (including basically every arithmetic operator).

test/Transforms/SCCP/constant-struct.ll

33

A little bit more test coverage would be nice... maybe a case which exercise the isOverdefined() path, and a case where the initial value is an argument or something else defined?

[davide]

In D22269#481969, @eli.friedman wrote:

You probably want to refactor this if you're planning to use it from IPSCCP... but you can do that in the followup, I guess.

Yes, I'll refactor separately.

In terms of expanding the struct code for vectors, I guess that might work? It's probably a lot of work for not much benefit, though; it would involve touching every single operation which can work on vectors (including basically every arithmetic operator).

I'm still unsure as well. Now that I have a slightly better understanding of the pass I might try that and see where it goes. If it's too complicated I'll just avoid doing that.

[davide]

Improved test coverage as suggested by Eli

[eli.friedman]

LGTM.

[reames]

Minor post commit style comments. The patch title caught my eye so I took a quick read through.

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

1572 ↗

(On Diff #63720)

Why must it be that any non-constant must be undef? I suspect this is either a well known invariant in the code (with which I'm unfamiliar), or a possibly missing assert.

1580 ↗

(On Diff #63720)

Is there a helper function which could common out this shared code?

[davide]

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

1572 ↗

(On Diff #63720)

I have the algorithm out-of-cache but IIRC once the lattice solver runs there can't be values with an "undefined" lattice value, so, yes, this is an invariant maintained by the algorithm.

1580 ↗

(On Diff #63720)

I tried to factor out in a later commit (a while ago).

static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V)

Does that make sense to you?

lib/Transforms/Scalar/SCCP.cpp

   /// method should be use to handle this.  If this returns true, the solver
   /// should be rerun.
   bool ResolvedUndefsIn(Function &F);
 
   bool isBlockExecutable(BasicBlock *BB) const {
     return BBExecutable.count(BB);
   }
 
+  std::vector<LatticeVal> getStructLatticeValueFor(Value *V) const {
+    std::vector<LatticeVal> StructValues;
+    StructType *STy = dyn_cast<StructType>(V->getType());
+    assert(STy && "getStructLatticeValueFor() can be called only on structs");
+    for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
+      auto I = StructValueState.find(std::make_pair(V, i));
+      assert(I != StructValueState.end() && "Value not in valuemap!");
+      StructValues.push_back(I->second);
+    }
+    return StructValues;
+  }
+
   LatticeVal getLatticeValueFor(Value *V) const {
     DenseMap<Value*, LatticeVal>::const_iterator I = ValueState.find(V);
     assert(I != ValueState.end() && "V is not in valuemap!");
     return I->second;
   }
 
   /// getTrackedRetVals - Get the inferred return value map.
   ///

     // Iterate over all of the instructions in a function, replacing them with
     // constants if we have found them to be of constant values.
     //
     for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) {
       Instruction *Inst = &*BI++;
       if (Inst->getType()->isVoidTy() || isa<TerminatorInst>(Inst))
         continue;
 
-      // TODO: Reconstruct structs from their elements.
-      if (Inst->getType()->isStructTy())
-        continue;
-
-      LatticeVal IV = Solver.getLatticeValueFor(Inst);
-      if (IV.isOverdefined())
-        continue;
+      Constant *Const = nullptr;
+      if (Inst->getType()->isStructTy()) {
+        std::vector<LatticeVal> IVs = Solver.getStructLatticeValueFor(Inst);
+        if (std::any_of(IVs.begin(), IVs.end(),
+                        [](LatticeVal &LV) { return LV.isOverdefined(); }))
+          continue;
+        std::vector<Constant *> ConstVals;
+        StructType *ST = dyn_cast<StructType>(Inst->getType());
+        for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) {
+          LatticeVal V = IVs[i];
+          ConstVals.push_back(V.isConstant()
+                                  ? V.getConstant()
+                                  : UndefValue::get(ST->getElementType(i)));
+        }
+        Const = ConstantStruct::get(ST, ConstVals);
+      } else {
+        LatticeVal IV = Solver.getLatticeValueFor(Inst);
+        if (IV.isOverdefined())
+          continue;
 
-      Constant *Const = IV.isConstant()
-        ? IV.getConstant() : UndefValue::get(Inst->getType());
+        Const = IV.isConstant() ? IV.getConstant()
+                                : UndefValue::get(Inst->getType());
+      }
+      assert(Const && "Constant is nullptr here!");
       DEBUG(dbgs() << "  Constant: " << *Const << " = " << *Inst << '\n');
 
       // Replaces all of the uses of a variable with uses of the constant.
       Inst->replaceAllUsesWith(Const);
 
       // Delete the instruction.
       Inst->eraseFromParent();
 

test/Transforms/SCCP/constant-struct.ll

+; Test that constant structs are folded.
+; RUN: opt %s -sccp -S | FileCheck %s
+
+define internal {i64} @struct1() {
+  %a = insertvalue {i64} undef, i64 24, 0
+  ret {i64} %a
+}
+
+; CHECK: define internal { i64 } @struct1() {
+; CHECK-NEXT:   ret { i64 } { i64 24 }
+; CHECK-NEXT: }
+
+define internal {i64, i64} @struct2() {
+  %a = insertvalue {i64, i64} undef, i64 24, 0
+  ret {i64, i64} %a
+}
+
+; CHECK: define internal { i64, i64 } @struct2() {
+; CHECK-NEXT:  ret { i64, i64 } { i64 24, i64 undef }
+; CHECK-NEXT: }
+
+define internal {i64, i64, i64} @struct3(i64 %x) {
+  %a = insertvalue {i64, i64, i64} undef, i64 24, 0
+  %b = insertvalue {i64, i64, i64} %a, i64 36, 1
+  %c = insertvalue {i64, i64, i64} %b, i64 %x, 2
+  ret {i64, i64, i64} %c
+}
+
+; CHECK: define internal { i64, i64, i64 } @struct3(i64 %x) {
+; CHECK-NEXT:  %c = insertvalue { i64, i64, i64 } { i64 24, i64 36, i64 undef }, i64 %x, 2
+; CHECK-NEXT:  ret { i64, i64, i64 } %c
+; CHECK-NEXT: }
+
+; Test(s) for overdefined values.
+define internal {i64, i32} @struct4(i32 %x) {
+  %a = insertvalue {i64, i32} {i64 12, i32 24}, i32 %x, 1
+  ret {i64, i32} %a
+}
+
+; CHECK: define internal { i64, i32 } @struct4(i32 %x) {
+; CHECK-NEXT:  %a = insertvalue { i64, i32 } { i64 12, i32 24 }, i32 %x, 1
+; CHECK-NEXT:  ret { i64, i32 } %a
+; CHECK-NEXT: }
+
+define internal {i32} @struct5(i32 %x) {
+  %a = insertvalue {i32} undef, i32 %x, 0
+  ret {i32} %a
+}
+
+; CHECK: define internal { i32 } @struct5(i32 %x) {
+; CHECK-NEXT:  %a = insertvalue { i32 } undef, i32 %x, 0
+; CHECK-NEXT:  ret { i32 } %a
+; CHECK-NEXT: }
+
+
+define internal {i32} @struct6({i32} %x) {
+  %a = insertvalue {i32} %x, i32 12, 0
+  ret {i32} %a
+}
+
+; CHECK: define internal { i32 } @struct6({ i32 } %x) {
+; CHECK-NEXT:  ret { i32 } { i32 12 }
+; CHECK-NEXT: }
+
+define internal {i16} @struct7() {
+  %a = insertvalue {i16} {i16 4}, i16 7, 0
+  ret {i16} %a
+}
+
+; CHECK: define internal { i16 } @struct7() {
+; CHECK-NEXT:  ret { i16 } { i16 7 }
+; CHECK-NEXT: }