[CVP] Handle instructions with no user. No need to create CVPLattice state. This handles terminator instructions and more.

[trentxintong]

Summary

I tested this patch by compiling sqlite3.ll (clang -O3 -mllvm -disable-llvm-optzns sqlite3.c.)

opt -called-value-propagation sqlite3.ll -time-passes -f -o out.ll

I get 10+% speedup for the pass. I expect some of the gain come from skipping terminator instructions.

=== BEFORE THE PATCH ===
===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 0.5562 seconds (0.5582 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
   0.2485 ( 46.4%)   0.0120 ( 57.7%)   0.2605 ( 46.8%)   0.2615 ( 46.8%)  Bitcode Writer
   0.1607 ( 30.0%)   0.0079 ( 37.7%)   0.1685 ( 30.3%)   0.1693 ( 30.3%)  Called Value Propagation
   0.1262 ( 23.6%)   0.0009 (  4.5%)   0.1271 ( 22.9%)   0.1275 ( 22.8%)  Module Verifier
   0.5353 (100.0%)   0.0209 (100.0%)   0.5562 (100.0%)   0.5582 (100.0%)  Total

=== AFTER THE PATCH ===
===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 0.5338 seconds (0.5355 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
   0.2498 ( 48.6%)   0.0118 ( 59.3%)   0.2615 ( 49.0%)   0.2629 ( 49.1%)  Bitcode Writer
   0.1377 ( 26.8%)   0.0075 ( 37.8%)   0.1452 ( 27.2%)   0.1455 ( 27.2%)  Called Value Propagation
   0.1264 ( 24.6%)   0.0006 (  3.0%)   0.1270 ( 23.8%)   0.1271 ( 23.7%)  Module Verifier
   0.5139 (100.0%)   0.0199 (100.0%)   0.5338 (100.0%)   0.5355 (100.0%)  Total

[trentxintong]

Friendly Ping. Are there any problems with this patch ? Do I need to collect more #s ?

[trentxintong]

collect some numbers on sqlite3.c

[trentxintong]

Ping 2X. Thanks!

llvm/trunk/lib/Transforms/IPO/CalledValuePropagation.cpp

ChangedValues[MemGV] =
         MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));
   }
 
   /// Handle all other instructions. All other instructions are marked
   /// overdefined.
   void visitInst(Instruction &I,
                  DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
                  SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
+    // Simply bail if this instruction has no user.
+    if (I.use_empty())
+      return;
     auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
     ChangedValues[RegI] = getOverdefinedVal();
   }
 };
 } // namespace
 
 namespace llvm {
 /// A specialization of LatticeKeyInfo for CVPLatticeKeys. The generic solver