[LLVMdev] RFC: Tail call optimization X86

[Evan Cheng]

Hi Arnold,

This is a very good first step! Thanks! Comments below.

Evan

Index: test/CodeGen/X86/constant-pool-remat-0.ll
===================================================================
--- test/CodeGen/X86/constant-pool-remat-0.ll	(revision 42247)
+++ test/CodeGen/X86/constant-pool-remat-0.ll	(working copy)
@@ -1,8 +1,10 @@
; RUN: llvm-as < %s | llc -march=x86-64 | grep LCPI | count 3
; RUN: llvm-as < %s | llc -march=x86-64 -stats -info-output-file - |  
grep asm-printer | grep 6
; RUN: llvm-as < %s | llc -march=x86 -mattr=+sse2 | grep LCPI | count 3
-; RUN: llvm-as < %s | llc -march=x86 -mattr=+sse2 -stats -info- 
output-file - | grep asm-printer | grep 8
-
+; RUN: llvm-as < %s | llc -march=x86 -mattr=+sse2 -stats -info- 
output-file - | grep asm-printer | grep 9
+; change preceeding line form ... | grep 8 to ..| grep 9 since
+; with new fastcc has std call semantics causing a stack adjustment
+; after the function call

Not sure if I understand this. Can you illustrate with an example?

Index: include/llvm/Target/TargetLowering.h
===================================================================
--- include/llvm/Target/TargetLowering.h	(revision 42247)
+++ include/llvm/Target/TargetLowering.h	(working copy)
@@ -851,8 +851,18 @@
    virtual std::pair<SDOperand, SDOperand>
    LowerCallTo(SDOperand Chain, const Type *RetTy, bool RetTyIsSigned,
                bool isVarArg, unsigned CallingConv, bool isTailCall,
-              SDOperand Callee, ArgListTy &Args, SelectionDAG &DAG);
+              bool isNextInstRet, SDOperand Callee, ArgListTy &Args,
+              SelectionDAG &DAG);
+  // IsEligibleForTailCallElimination - Check whether the call is  
eligible for
+  // tailcall elimination
+  virtual bool IsEligibleForTailCallElimination(SelectionDAG& DAG,
+                                                bool IsNextInstRet,
+                                                SDOperand Callee,
+                                                unsigned CalleeCC)  
const {
+    return false;
+  }
+

I am not too keen on "isNextInstRet". We should never use instruction  
ordering before scheduling to determine whether it's possible to  
perform an optimization. IsEligibleForTailCallElimination() should  
determine the feasibility on its own, no?


+// check whether the instruction following the tailcall is a return  
instruction
+// and whether its return type is void or if it uses the value  
defined by the
+// tail call
+bool IsNextInstructionReturn(Instruction &I) {
+  bool IsNextInstRet = false;
+  BasicBlock *BB = I.getParent();
+  BasicBlock::iterator BI = &I;
+  assert(BI != BB->end() && "Woohooa");
+  ++BI;
+  if (BI != BB->end()) {
+    ReturnInst *RI = dyn_cast<ReturnInst>(BI);
+    if (RI) {
+      if (RI->getReturnValue()==0 ||
+          std::find(RI->op_begin(), RI->op_end(),
+                    (Value*)&I) != RI->op_end()) {
+        IsNextInstRet=true;
+      }
+    }
+  }
+  return IsNextInstRet;
+}
+

Some stylistic nitpicks. Please write the comments as:
/// IsNextInstructionReturn - Check whether..

+  assert(BI != BB->end() && "Woohooa");
Better assertion messages please. :-)

Why not write it like this:

+bool IsNextInstructionReturn(Instruction &I) {
+  BasicBlock *BB = I.getParent();
+  BasicBlock::iterator BI = &I;
+  assert(BI != BB->end() && "Woohooa");
+  ++BI;
+  if (BI != BB->end()) {
+    if (ReturnInst *RI = dyn_cast<ReturnInst>(BI)) {
+      if (RI->getReturnValue()==0 ||
+          std::find(RI->op_begin(), RI->op_end(),
+                    (Value*)&I) != RI->op_end())
+        return true;
+    }
+  }
+  return false;
+}

Also, shouldn't this function be "static"?

let isCall = 1, isTerminator = 1, isReturn = 1, isBarrier = 1 in
+  def TAILJMPd : IBr<0xE9, (ins i32imm:$dst), "jmp\t${dst:call}  #  
TAILCALL",
+                 []>;
+let isCall = 1, isTerminator = 1, isReturn = 1, isBarrier = 1 in
+  def TAILJMPr : I<0xFF, MRM4r, (outs), (ins GR32:$dst), "jmp{l}\t{*} 
$dst  # TAILCALL",
+                 []>;
+let isCall = 1, isTerminator = 1, isReturn = 1, isBarrier = 1 in
    def TAILJMPm : I<0xFF, MRM4m, (outs), (ins i32mem:$dst),
                     "jmp\t{*}$dst  # TAIL CALL", []>;

Please fix the inconsistency: "TAILCALL" vs. "TAIL CALL".

+SDOperand GetPossiblePreceedingTailCall(SDOperand Chain) {

This should be "static"?

+
+  Chain = DAG.getNode( X86ISD::CALL,
                        NodeTys, &Ops[0], Ops.size());

Stylistic nitpick: please merge 2 lines and remove the space after '('.

-    Chain = DAG.getNode(X86ISD::FP_SET_RESULT, Tys, Ops, 2);
-    Flag = Chain.getValue(1);
+      Chain = DAG.getNode(X86ISD::FP_SET_RESULT, Tys, Ops, 2);
+      Flag = Chain.getValue(1);

What happened here?


+// Check to see whether the next instruction following the call is a  
return
+// A function is eligible if caller/callee calling conventions  
match, currently
+// only fastcc supports tail calls, and the function CALL is  
immediatly followed
+// by a RET
+bool X86TargetLowering::IsEligibleForTailCallElimination 
(SelectionDAG& DAG,
+                                                         bool  
IsNextInstRet,
+                                                         SDOperand  
Callee,
+                                                         unsigned  
CalleeCC)
+  const {

Having "const {" on a separate line looks funky. :-)

+  bool IsEligible = false;
+  //if (IsNextInstRet && false == Subtarget->is64Bit()) {

Please remove code that's commented out.

+        if(  G != 0 &&
+             (GV = G->getGlobal()) &&
+             (GV->hasHiddenVisibility() || GV->hasProtectedVisibility 
()))
+          IsEligible=true;
+        else
+        IsEligible=false;

if( G  ==> if (G  :-)

No need to set IsEligible to false since it's initialized to false.

Evan

On Sep 23, 2007, at 9:58 AM, Arnold Schwaighofer wrote:

> The patch is against revision 42247.
> <tailcall-src.patch>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev