[TailCallElim] Add handling of readonly functions

[laytonio]

Summary

We can perform accumulator recursion on values loaded from memory, if we verify that the memory isn't modified before the function would have returned.

[laytonio]

noticed minor typo in the regression test

[efriedma]

I'm concerned that hoisting instructions to the entry block isn't safe. A load can have undefined behavior, and you don't try to prove the load in question points to a valid address. Is there some way to make this transform work without hoisting the operations to the entry block? At first glance, it seems like it should be possible to instead sink the instructions into the return block. But I haven't thought about it very carefully.

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp

391

While you're in this area, the following currently crashes opt -tailcallelim:

define i32 @f() local_unnamed_addr {
entry:
  %call = call i32 @g()
  switch i32 %call, label %sw.default [
    i32 1, label %cleanup
    i32 5, label %cleanup
    i32 7, label %cleanup
  ]

sw.default:
  %call1 = call i32 @f()
  %add = add nsw i32 %call1, 1
  br label %cleanup

cleanup:
  %retval.0 = phi i32 [ %add, %sw.default ], [ %call, %entry ], [ %call, %entry ], [ %call, %entry ]
  ret i32 %retval.0
}

declare i32 @g()

Please take a look, since it seems related to what you're doing.

400

llvm::all_of.

[laytonio]

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp

391

I created a separate diff for this fix. https://reviews.llvm.org/D78765

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp

static bool canMoveAboveCall(Instruction *I, CallInst *CI, AliasAnalysis *AA) {
   // the call, or movable instructions between the call and the instruction
   // itself.
   return !is_contained(I->operands(), CI);
 }
 
 /// Return true if the specified value is the same when the return would exit
 /// as it was when the initial iteration of the recursive function was executed.
 ///
-/// We currently handle static constants and arguments that are not modified as
-/// part of the recursion.
+/// We currently handle
+///   * static constants
+///   * arguments that are not modified as part of the recursion
+///   * returns only reachable from one case of a switch on a value
+///   * in readonly functions, GEPs and loads where all operands are dyn const
 static bool isDynamicConstant(Value *V, CallInst *CI, ReturnInst *RI) {
   if (isa<Constant>(V)) return true; // Static constants are always dyn consts
 
   // Check to see if this is an immutable argument, if so, the value
   // will be available to initialize the accumulator.
   if (Argument *Arg = dyn_cast<Argument>(V)) {
     // Figure out which argument number this is...
     unsigned ArgNo = 0;
static bool isDynamicConstant(Value *V, CallInst *CI, ReturnInst *RI) {
   }
 
   // Switch cases are always constant integers. If the value is being switched
   // on and the return is only reachable from one of its cases, it's
   // effectively constant.
   if (BasicBlock *UniquePred = RI->getParent()->getUniquePredecessor())
     if (SwitchInst *SI = dyn_cast<SwitchInst>(UniquePred->getTerminator()))
       if (SI->getCondition() == V)
         return SI->getDefaultDest() != RI->getParent();
 
-  // Not a constant or immutable argument, we can't safely transform.
+  // In readonly functions, GEPs and loads where all operands are
+  // dynamic constant are also dynamic constant
+  if (CI->onlyReadsMemory()) {
+    if (isa<LoadInst>(V) || isa<GetElementPtrInst>(V)) {
+      Instruction *I = cast<Instruction>(V);
+
+      bool OpsAreDynConsts = true;
+      for (Value *Op : I->operand_values()) {
+        OpsAreDynConsts = isDynamicConstant(Op, CI, RI);
+        if (!OpsAreDynConsts)
+          break;
+      }
+      if (OpsAreDynConsts)
+        return true;
+    }
+  }
+
+  // we can't safely transform.
   return false;
 }
 
 /// Check to see if the function containing the specified tail call consistently
 /// returns the same runtime-constant value at all exit points except for
 /// IgnoreRI. If so, return the returned value.
 static Value *getCommonReturnValue(ReturnInst *IgnoreRI, CallInst *CI) {
   Function *F = CI->getParent()->getParent();
for (; I != E && FI != FE; ++I, ++FI)
       if (*I != &*FI) break;
     if (I == E && FI == FE)
       return nullptr;
   }
 
   return CI;
 }
 
+static void moveInstAndDepsToEntry(Instruction *I, Function *F) {
+  // This is only safe if the instruction is dynamic constant,
+  // which should alway be true if we are here.
+
+  Instruction *Front = &F->getEntryBlock().front();
+  I->moveBefore(Front);
+
+  for (Value *Op : I->operand_values()) {
+    if (Instruction *OpI = dyn_cast<Instruction>(Op)) {
+      if (I == OpI) {
+        // This can happen if the instruction had an operand that was a
+        // dynamic constant argument and we replaced it with a PHI that
+        // selects itself
+        continue;
+      }
+
+      moveInstAndDepsToEntry(OpI, F);
+    }
+  }
+}
+
 static bool eliminateRecursiveTailCall(
     CallInst *CI, ReturnInst *Ret, BasicBlock *&OldEntry,
     bool &TailCallsAreMarkedTail, SmallVectorImpl<PHINode *> &ArgumentPHIs,
     AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU) {
   // If we are introducing accumulator recursion to eliminate operations after
   // the call instruction that are both associative and commutative, the initial
   // value for the accumulator is placed in this variable.  If this value is set
   // then we actually perform accumulator recursion elimination instead of
if (AccumulatorRecursionEliminationInitVal) {
     // Loop over all of the predecessors of the tail recursion block.  For the
     // real entry into the function we seed the PHI with the initial value,
     // computed earlier.  For any other existing branches to this block (due to
     // other tail recursions eliminated) the accumulator is not modified.
     // Because we haven't added the branch in the current block to OldEntry yet,
     // it will not show up as a predecessor.
     for (pred_iterator PI = PB; PI != PE; ++PI) {
       BasicBlock *P = *PI;
-      if (P == &F->getEntryBlock())
-        AccPN->addIncoming(AccumulatorRecursionEliminationInitVal, P);
-      else
+      if (P == &F->getEntryBlock()) {
+        Value *AccRecElimInitVal = AccumulatorRecursionEliminationInitVal;
+        // If the initial value is an instruction, then we need to move it and
+        // its dependencies to the entry so it is available to the PHI. If we
+        // have gotten here then we know that the instruction is dynamic
+        // constant and thus is safe to move.
+        if (Instruction *I = dyn_cast<Instruction>(AccRecElimInitVal))
+          moveInstAndDepsToEntry(I, F);
+
+        AccPN->addIncoming(AccRecElimInitVal, P);
+      } else {
         AccPN->addIncoming(AccPN, P);
       }
+    }
 
     if (AccRecInstr) {
       // Add an incoming argument for the current block, which is computed by
       // our associative and commutative accumulator instruction.
       AccPN->addIncoming(AccRecInstr, BB);
 
       // Next, rewrite the accumulator recursion instruction so that it does not
       // use the result of the call anymore, instead, use the PHI node we just

llvm/test/Transforms/TailCallElim/accum_recursion.ll

; CHECK: add nsw i64 %accumulator.tr, %1
   ret i64 %4
 ; CHECK: br label %tailrecurse
 
 bb2:
 ; CHECK: bb2:
   ret i64 %n
 ; CHECK: ret i64 %accumulator.tr
 }
+
+%struct.Relative = type { i32, [5 x i8] }
+
+define i32 @test4_readonly(%struct.Relative* %relativePtr, i32 %index) nounwind readonly {
+; CHECK-LABEL: @test4_readonly(
+entry:
+; CHECK: %0 = getelementptr inbounds %struct.Relative, %struct.Relative* %relativePtr, i64 0, i32 0
+; CHECK: %1 = load i32, i32* %0, align 4
+; CHECK: tailrecurse:
+; CHECK: %accumulator.tr = phi i32 [ %1, %entry ]
+; CHECK: %index.tr = phi i32 [ %index, %entry ]
+  %0 = icmp eq i32 %index, 0
+  br i1 %0, label %then, label %else
+
+then:
+  %1 = getelementptr inbounds %struct.Relative, %struct.Relative* %relativePtr, i64 0, i32 0
+  %2 = load i32, i32* %1, align 4
+  ret i32 %2
+
+else:
+  %3 = add i32 %index, -1
+  %4 = zext i32 %3 to i64
+  %5 = getelementptr inbounds %struct.Relative, %struct.Relative* %relativePtr, i64 0, i32 1, i64 %4
+  %6 = load i8, i8* %5, align 1
+  %7 = zext i8 %6 to i32
+  %8 = call i32 @test4_readonly(%struct.Relative* %relativePtr, i32 %3)
+; CHECK-NOT: call i32:
+  %9 = add i32 %8, %7
+  ret i32 %9
+}