Merge pull request #2550 from AndyAyersMS/InlineTree

Initial version of the inline tree

6 files changed, 229 insertions, 27 deletions

diff --git a/src/jit/block.cpp b/src/jit/block.cpp
index 15e6df01c4..9149bbe11b 100644
--- a/src/jit/block.cpp
+++ b/src/jit/block.cpp
@@ -637,3 +637,69 @@ unsigned PtrKeyFuncs<BasicBlock>::GetHashCode(const BasicBlock* ptr)
     return ptr->bbNum;
 }
 
+//------------------------------------------------------------------------
+// inlExpLst: default constructor for an inlExpList
+//
+// Notes: use for the root instance. We set ixlCode to nullptr here
+// (rather than the IL buffer address of the root method) to preserve
+// existing behavior, which is to allow one recursive inline.
+
+inlExpLst::inlExpLst() : ixlParent(nullptr), ixlChild(nullptr), 
+                         ixlSibling(nullptr), ilOffset(BAD_IL_OFFSET), 
+                         ixlCode(nullptr)
+{
+#ifdef DEBUG
+   methodName = nullptr;
+   depth = 0;
+#endif
+}
+
+
+#ifdef DEBUG
+
+//------------------------------------------------------------------------
+// Dump: Dump an inlExpLst entry and all descendants to stdout
+//
+// Arguments:
+//    indent: indentation level for this node
+
+void inlExpLst::Dump(int indent)
+{
+    // Handle fact that siblings are in reverse order.
+    if (ixlSibling != nullptr) 
+    {
+        ixlSibling->Dump(indent);
+    }
+    
+    // Dump this node
+    if (ixlParent == nullptr)
+    {
+        // root
+        printf("Inlines into %s\n", methodName);
+    }
+    else 
+    {
+        for (int i = 0; i < indent; i++) 
+        { 
+            printf(" ");
+        }
+        
+        if (ilOffset == BAD_IL_OFFSET) 
+        {
+            printf("[IL=?] %s\n", methodName);
+        }
+        else 
+        {
+            IL_OFFSET offset = jitGetILoffs(ilOffset);
+            printf("[IL=%d] %s\n", offset, methodName);
+        }
+    }
+    
+    // Recurse to first child
+    if (ixlChild != nullptr) 
+    {
+        ixlChild->Dump(indent + 2);
+    }
+}
+#endif
+
diff --git a/src/jit/block.h b/src/jit/block.h
index e8fd0e9854..7ed74933d1 100644
--- a/src/jit/block.h
+++ b/src/jit/block.h
@@ -159,8 +159,22 @@ struct EntryState
 
 struct inlExpLst
 {
-    inlExpLst*      ixlNext;
-    BYTE*           ixlCode;
+   // Default constructor, suitable for root instance
+   inlExpLst();
+
+   inlExpLst*      ixlParent;    // logical caller (parent)
+   inlExpLst*      ixlChild;     // first child
+   inlExpLst*      ixlSibling;   // next child of the parent
+   IL_OFFSETX      ilOffset;     // call site location within parent
+   BYTE*           ixlCode;      // address of IL buffer for the method
+
+#ifdef DEBUG
+   const char *    methodName;
+   unsigned        depth;
+
+   // Dump this entry and all descendants
+   void Dump(int indent = 0);
+#endif
 };
 
 typedef inlExpLst* inlExpPtr;
diff --git a/src/jit/compiler.h b/src/jit/compiler.h
index 1c2a54e5b0..295ea1cc10 100644
--- a/src/jit/compiler.h
+++ b/src/jit/compiler.h
@@ -4772,7 +4772,8 @@ private:
     unsigned            fgBigOffsetMorphingTemps[TYP_COUNT];
 
     static bool         fgIsUnboundedInlineRecursion(inlExpPtr expLst,
-                                                     BYTE *    ilCode);
+                                                     BYTE *    ilCode,
+                                                     DWORD&    depth);
 
     JitInlineResult     fgInvokeInlineeCompiler(GenTreeCall*   call);
     void                fgInsertInlineeBlocks (InlineInfo * pInlineInfo);
@@ -4813,15 +4814,9 @@ private:
     bool                gtIsTypeHandleToRuntimeTypeHelper(GenTreePtr tree);
     bool                gtIsActiveCSE_Candidate(GenTreePtr tree);
 
-    //--------------- The following are used when copying trees ---------------
-
-    inlExpPtr           fgInlineExpList;
-
-    int                 fgInlCount;
-    int                 fgInlQMarkCount;
-
 #ifdef DEBUG
     unsigned            fgInlinedCount; // Number of successful inline expansion of this method.
+    bool                fgPrintInlinedMethods;
 #endif
     
     bool fgIsBigOffset(size_t offset);
diff --git a/src/jit/flowgraph.cpp b/src/jit/flowgraph.cpp
index bd1f559f51..754755338f 100644
--- a/src/jit/flowgraph.cpp
+++ b/src/jit/flowgraph.cpp
@@ -32,6 +32,8 @@ void                Compiler::fgInit()
 
 #ifdef DEBUG
     fgInlinedCount               = 0;
+    static ConfigDWORD fJitPrintInlinedMethods;
+    fgPrintInlinedMethods = fJitPrintInlinedMethods.val(CLRConfig::EXTERNAL_JitPrintInlinedMethods) == 1;
 #endif // DEBUG
 
     /* We haven't yet computed the bbPreds lists */
@@ -21485,19 +21487,21 @@ void Compiler::fgRemoveContainedEmbeddedStatements(GenTreePtr tree, GenTreeStmt*
 /*****************************************************************************
  * Check if we have a recursion loop or if the recursion is too deep while doing the inlining.
  * Return true if a recursion loop is found or if the inlining recursion is too deep.
+ * Also return the depth.
  */
 
 bool          Compiler::fgIsUnboundedInlineRecursion(inlExpPtr               expLst,
-                                                     BYTE*                   ilCode)
+                                                     BYTE*                   ilCode,
+                                                     DWORD&                  depth)
 {
     const DWORD MAX_INLINING_RECURSION_DEPTH = 20;
 
-    DWORD count = 0;
-    for (; expLst; expLst = expLst->ixlNext)
+    depth = 0;
+    for (; expLst != nullptr; expLst = expLst->ixlParent)
     {
         // Hard limit just to catch pathological cases
-        count++;
-        if  ((expLst->ixlCode == ilCode) || (count > MAX_INLINING_RECURSION_DEPTH))
+        depth++;
+        if  ((expLst->ixlCode == ilCode) || (depth > MAX_INLINING_RECURSION_DEPTH))
             return true;
     }
 
@@ -21521,7 +21525,27 @@ void                Compiler::fgInline()
 #endif // DEBUG
 
     BasicBlock* block = fgFirstBB;
-    noway_assert(block);
+    noway_assert(block != nullptr);
+
+    // Set the root inline context on all statements
+    inlExpLst* expDsc = new (this, CMK_Inlining) inlExpLst();
+
+#if defined(DEBUG)
+    expDsc->methodName = info.compFullName;
+#endif
+
+    for (; block != nullptr; block = block->bbNext)
+    {
+        for (GenTreeStmt* stmt = block->firstStmt();
+             stmt;
+             stmt = stmt->gtNextStmt)
+        {
+           stmt->gtInlineExpList = expDsc;
+        }
+    }
+
+    // Reset block back to start for inlining
+    block = fgFirstBB;
 
     do
     {
@@ -21603,6 +21627,12 @@ void                Compiler::fgInline()
         fgDispHandlerTab();
     }
 
+    if  (verbose || (fgInlinedCount > 0 && fgPrintInlinedMethods))
+    {
+       printf("**************** Inline Tree\n");
+       expDsc->Dump();
+    }
+
 #endif // DEBUG
 }
 
@@ -21895,7 +21925,10 @@ JitInlineResult       Compiler::fgInvokeInlineeCompiler(GenTreeCall* call)
     // Store the link to inlineCandidateInfo into inlineInfo
     inlineInfo.inlineCandidateInfo = inlineCandidateInfo;
 
-    if (fgIsUnboundedInlineRecursion(inlineInfo.iciStmt->gtStmt.gtInlineExpList, inlineCandidateInfo->methInfo.ILCode))
+    DWORD inlineDepth = 0;
+    BYTE * candidateIL = inlineCandidateInfo->methInfo.ILCode;
+    inlExpPtr expList = inlineInfo.iciStmt->gtStmt.gtInlineExpList;
+    if (fgIsUnboundedInlineRecursion(expList, candidateIL, inlineDepth))
     {
 #ifdef DEBUG
         if (verbose)
@@ -22069,14 +22102,12 @@ JitInlineResult       Compiler::fgInvokeInlineeCompiler(GenTreeCall* call)
 #ifdef DEBUG
     ++fgInlinedCount;
 
-    static ConfigDWORD fJitPrintInlinedMethods;
-
-    if (verbose ||
-        fJitPrintInlinedMethods.val(CLRConfig::EXTERNAL_JitPrintInlinedMethods) == 1)
+    if (verbose || fgPrintInlinedMethods)
     {
-        printf("Successfully inlined %s (%d IL bytes) into %s\n",
+        printf("Successfully inlined %s (%d IL bytes) (depth %d) into %s\n",
                eeGetMethodFullName(fncHandle),
                inlineCandidateInfo->methInfo.ILCodeSize,
+               inlineDepth,
                info.compFullName);
     }
 
@@ -22145,13 +22176,25 @@ void Compiler::fgInsertInlineeBlocks(InlineInfo* pInlineInfo)
     //
     // Obtain an inlExpLst struct and update the gtInlineExpList field in the inlinee's statements
     //
-    inlExpLst* expDsc;
-    expDsc = new (this, CMK_Inlining) inlExpLst;
-    expDsc->ixlCode = pInlineInfo->inlineCandidateInfo->methInfo.ILCode;
-    expDsc->ixlNext = iciStmt->gtStmt.gtInlineExpList;
+    inlExpLst* expDsc = new (this, CMK_Inlining) inlExpLst;
+    inlExpLst *parentLst = iciStmt->gtStmt.gtInlineExpList;
+    noway_assert(parentLst != nullptr);
+    BYTE *parentIL = pInlineInfo->inlineCandidateInfo->methInfo.ILCode;
+    expDsc->ixlCode = parentIL;
+    expDsc->ixlParent = parentLst;
+    // Push on front here will put siblings in reverse lexical
+    // order which we undo in the dumper
+    expDsc->ixlSibling = parentLst->ixlChild;
+    parentLst->ixlChild = expDsc;
+    expDsc->ixlChild = nullptr;
+    expDsc->ilOffset = iciStmt->AsStmt()->gtStmtILoffsx;
+#ifdef DEBUG
+    expDsc->methodName = eeGetMethodFullName(pInlineInfo->fncHandle);
+    expDsc->depth = parentLst->depth + 1;
+#endif
 
     for (block = InlineeCompiler->fgFirstBB;
-         block;
+         block != nullptr;
          block = block->bbNext)
     {
         for (GenTreeStmt* stmt = block->firstStmt();
diff --git a/tests/src/JIT/opt/Inline/tests/fact.cs b/tests/src/JIT/opt/Inline/tests/fact.cs
new file mode 100644
index 0000000000..113cdc291f
--- /dev/null
+++ b/tests/src/JIT/opt/Inline/tests/fact.cs
@@ -0,0 +1,36 @@
+// Copyright (c) Microsoft. All rights reserved.
+// Licensed under the MIT license. See LICENSE file in the project root for full license information.
+
+using System;
+
+class Fact {
+    static int factTR(int n, int a) {
+        if (n <= 1) return a;
+        return factTR(n - 1, a * n);
+    }
+    
+    static int fact(int n) {
+        return factTR(n, 1);
+    }
+
+    static int factR(int n) {
+        if (n <= 1) return 1;
+        return n * factR(n - 1);
+    }
+
+    static int factRx(int n, int a = 0, int b = 0, int c = 0) {
+        if (n <= 1) return 1;
+        return n * factRx(n - 1, a, b, c);
+    }
+
+    public static int Main() {
+        int resultTR = fact(6);
+        int resultR = factR(6);
+        int resultRx = factRx(6);
+        Console.WriteLine("fact(6) = {0}", resultTR);
+        Console.WriteLine("factR(6) = {0}", resultR);
+        Console.WriteLine("factRx(6) = {0}", resultRx);
+        bool good = resultTR == resultR && resultTR == resultRx && resultR == 720;
+        return (good ? 100 : -1);
+    }
+}
diff --git a/tests/src/JIT/opt/Inline/tests/fact.csproj b/tests/src/JIT/opt/Inline/tests/fact.csproj
new file mode 100644
index 0000000000..656f7b7e06
--- /dev/null
+++ b/tests/src/JIT/opt/Inline/tests/fact.csproj
@@ -0,0 +1,48 @@
+<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="12.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.props))\dir.props" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <AssemblyName>$(MSBuildProjectName)</AssemblyName>
+    <SchemaVersion>2.0</SchemaVersion>
+    <ProjectGuid>{95DFC527-4DC1-495E-97D7-E94EE1F7140D}</ProjectGuid>
+    <OutputType>Exe</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <FileAlignment>512</FileAlignment>
+    <ProjectTypeGuids>{786C830F-07A1-408B-BD7F-6EE04809D6DB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}</ProjectTypeGuids>
+    <ReferencePath>$(ProgramFiles)\Common Files\microsoft shared\VSTT	.0\UITestExtensionPackages</ReferencePath>
+    <SolutionDir Condition="$(SolutionDir) == '' Or $(SolutionDir) == '*Undefined*'">..\..\</SolutionDir>
+    <RestorePackages>true</RestorePackages>
+    <NuGetPackageImportStamp>7a9bfb7d</NuGetPackageImportStamp>
+  </PropertyGroup>
+  <!-- Default configurations to help VS understand the configurations -->
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+  </PropertyGroup>
+  <ItemGroup>
+    <CodeAnalysisDependentAssemblyPaths Condition=" '$(VS100COMNTOOLS)' != '' " Include="$(VS100COMNTOOLS)..\IDE\PrivateAssemblies">
+      <Visible>False</Visible>
+    </CodeAnalysisDependentAssemblyPaths>
+  </ItemGroup>
+  <PropertyGroup>
+    <DebugType>None</DebugType>
+  </PropertyGroup>
+  <ItemGroup>
+    <Compile Include="fact.cs" />
+  </ItemGroup>
+  <ItemGroup>
+    <None Include="$(JitPackagesConfigFileDirectory)minimal\project.json" />
+  </ItemGroup>
+  <ItemGroup>
+    <Service Include="{82A7F48D-3B50-4B1E-B82E-3ADA8210C358}" />
+  </ItemGroup>
+  <PropertyGroup>
+    <ProjectJson>$(JitPackagesConfigFileDirectory)minimal\project.json</ProjectJson>
+    <ProjectLockJson>$(JitPackagesConfigFileDirectory)minimal\project.lock.json</ProjectLockJson>
+  </PropertyGroup>
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.targets))\dir.targets" />
+  <PropertyGroup Condition=" '$(MsBuildProjectDirOverride)' != '' ">
+  </PropertyGroup> 
+</Project>