[CloneFunction] Simplify previously unsimplifiable instructions

[anna]

Summary

Sometimes during clone function, we may not be able to simplify during
the first phase of cloning: CloneBlock. This is because the instruction
may not be tied to any basic block yet (as the case when cloning is
called during inlining).

This patch adds all instructions from the cloned function into the
second pass of simplification, which is done after the instructions are
tied to basic block. We reuse the second pass which was previously handling phi
nodes and their uses.

The benefit of this patch is to simplify the instructions that are
inlined from the callee to the caller, so that later passes after
inlining have fewer instructions to churn on (see test case for example).

[hfinkel]

Is there any compile-time impact? Should we just simplify all instructions at this later point instead of having two passes?

[anna]

In D52362#1242200, @hfinkel wrote:

Is there any compile-time impact?

I haven't checked the compile time impact. Will do. However, this is just a linear addition of instructions and it's uses - we were already looking at phis and their uses. Also, later passes (that iterate over the inlined instructions) will anyway iterate over all instructions. So, I think it should be either neutral or a win. Win when we were wastefully iterating over instructions through multiple passes until we reached the pass which could simplify these instructions.

Should we just simplify all instructions at this later point instead of having two passes?

I'll take a look, but it seems a more invasive change. We first cloneBlocks, then iterate over all instructions in the callee and insert it in the caller in right order (now the instructions have a parent block), and then have two passes over the PHINodes. The second pass over the PHINode already looks over the uses and does recursive simplification. To this list, now that all instructions have basic block parents, we add them for recursive simplification.

[hfinkel]

In D52362#1242539, @anna wrote:

In D52362#1242200, @hfinkel wrote:

Is there any compile-time impact?

I haven't checked the compile time impact. Will do. However, this is just a linear addition of instructions and it's uses - we were already looking at phis and their uses. Also, later passes (that iterate over the inlined instructions) will anyway iterate over all instructions. So, I think it should be either neutral or a win. Win when we were wastefully iterating over instructions through multiple passes until we reached the pass which could simplify these instructions.

Should we just simplify all instructions at this later point instead of having two passes?

I'll take a look, but it seems a more invasive change. We first cloneBlocks, then iterate over all instructions in the callee and insert it in the caller in right order (now the instructions have a parent block), and then have two passes over the PHINodes. The second pass over the PHINode already looks over the uses and does recursive simplification. To this list, now that all instructions have basic block parents, we add them for recursive simplification.

That makes sense. SimplyInstruction can, potentially, get expensive. If there's no compile-time impact of the change, then this probably doesn't matter. If there does seem to be a compile-time impact, then you might want to look into making it, overall, use only one simplification phase.

[anna]

Results on CTMark does show negative compile time impact on couple of benchmarks - run on a haswell machine over 4 runs with and without patch:

Tests: 10
Metric: compile_time

Program                                         Base    Patch   diff 
                                                                 
Bullet/bullet                                  59.27  67.88 14.5%
tramp3d-v4/tramp3d-v4                          56.98  64.87 13.8%
7zip/7zip-benchmark                            91.63 103.92 13.4%
kimwitu++/kc                                   31.60  35.39 12.0%
lencod/lencod                                  41.75  43.57  4.4%
sqlite3/sqlite3                                40.47  40.02 -1.1%
SPASS/SPASS                                    34.11  34.33  0.6%
mafft/pairlocalalign                           23.81  23.71 -0.4%
consumer-typeset/consumer-typeset              26.28  26.22 -0.2%
ClamAV/clamscan                                37.51  37.54  0.1%

Maybe we're hitting on the degenerate case - Ran SimplifyInstruction, but no change in simplification. So future passes still had to iterate on same number of instructions...

[anna]

abandon revision - too old and context lost.

lib/Transforms/Utils/CloneFunction.cpp

#endif
   }
 
   // Loop over all of the basic blocks in the old function.  If the block was
   // reachable, we have cloned it and the old block is now in the value map:
   // insert it into the new function in the right order.  If not, ignore it.
   //
   // Defer PHI resolution until rest of function is resolved.
   SmallVector<const PHINode*, 16> PHIToResolve;
+  std::vector<const BasicBlock*> ReachableBBsInOldFunc;
   for (const BasicBlock &BI : *OldFunc) {
     Value *V = VMap.lookup(&BI);
     BasicBlock *NewBB = cast_or_null<BasicBlock>(V);
     if (!NewBB) continue;  // Dead block.
 
+    // This was a reachable BB from the StartingBB.
+    ReachableBBsInOldFunc.push_back(&BI);
     // Add the new block to the new function.
     NewFunc->getBasicBlockList().push_back(NewBB);
 
     // Handle PHI nodes specially, as we have to remove references to dead
     // blocks.
     for (const PHINode &PN : BI.phis()) {
       // PHI nodes may have been remapped to non-PHI nodes by the caller or
       // during the cloning process.
#endif
   // mapping will just map us to the new node (which may not even be a PHI
   // node).
   const DataLayout &DL = NewFunc->getParent()->getDataLayout();
   SmallSetVector<const Value *, 8> Worklist;
   for (unsigned Idx = 0, Size = PHIToResolve.size(); Idx != Size; ++Idx)
     if (isa<PHINode>(VMap[PHIToResolve[Idx]]))
       Worklist.insert(PHIToResolve[Idx]);
 
+  // In this second pass, we also add all instructions reachable from
+  // StartingInst.  This allows simplification of instructions that previously
+  // could not be simplified because they were not tied to any basic block.
+  for (auto &I: make_range(StartingInst->getIterator(), StartingBB->end()))
+     Worklist.insert(&I);
+
+  for (auto *BB: ReachableBBsInOldFunc) {
+    if (BB == StartingBB)
+      continue;
+    for (auto &I: *BB)
+      Worklist.insert(&I);
+  }
   // Note that we must test the size on each iteration, the worklist can grow.
   for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
     const Value *OrigV = Worklist[Idx];
     auto *I = dyn_cast_or_null<Instruction>(VMap.lookup(OrigV));
     if (!I)
       continue;
 
     // Skip over non-intrinsic callsites, we don't want to remove any nodes from

test/Transforms/Inline/inline_inv_group.ll

 ; RUN: opt < %s -inline -S | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define i8* @callee() alwaysinline {
-; CHECK-LABEL: define i8* @callee()
     %1 = call i8* @llvm.strip.invariant.group.p0i8(i8* null)
     ret i8* %1
 }
 
 define i8* @caller() {
 ; CHECK-LABEL: define i8* @caller()
-; CHECK-NEXT: call i8* @llvm.strip.invariant.group.p0i8(i8* null)
+; CHECK-NEXT: ret i8* null
     %1 = call i8* @callee()
     ret i8* %1
 }
 
 declare i8* @llvm.strip.invariant.group.p0i8(i8*)