JIT: Add BinaryTrees benchmark variant

Add a variant that uses a class and out parameter instead of returning
a struct by value. This variant is similar to version 3 from the benchmarks
games site, but with validation added and parallelism removed.

See related analysis in #8837. According to xunit-perf runs, this version's
performance is improved (~10%) by enabling the model inlining policy. When
the model policy is enabled the inliner will inline the two outermost calls
to `ChildTreeNodes` in the innermlost loop.

Also, make sure the new and the original version to build the same way in
release and debug.

4 files changed, 191 insertions, 0 deletions

diff --git a/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csharp.cs b/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csharp.cs
index c77e802989..05dbe94f09 100644
--- a/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csharp.cs
+++ b/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csharp.cs
@@ -16,6 +16,7 @@ using Xunit;
 
 [assembly: OptimizeForBenchmarks]
 [assembly: MeasureInstructionsRetired]
+[assembly: MeasureGCCounts]
 
 namespace BenchmarksGame
 {
diff --git a/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csharp3.cs b/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csharp3.cs
new file mode 100644
index 0000000000..6dcf48a422
--- /dev/null
+++ b/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csharp3.cs
@@ -0,0 +1,142 @@
+// Licensed to the .NET Foundation under one or more agreements.
+// The .NET Foundation licenses this file to you under the MIT license.
+// See the LICENSE file in the project root for more information.
+/* The Computer Language Benchmarks Game
+   http://benchmarksgame.alioth.debian.org/
+
+   Based on code originally contributed by Marek Safar
+   and optimized by kasthack
+
+   modified for use with xunit-performance
+*/
+
+using Microsoft.Xunit.Performance;
+using System;
+using System.Runtime.CompilerServices;
+using Xunit;
+
+[assembly: OptimizeForBenchmarks]
+[assembly: MeasureInstructionsRetired]
+[assembly: MeasureGCCounts]
+
+namespace BenchmarksGame
+{
+public class BinaryTrees3
+{
+    private const int minDepth = 4;
+    private const int Iterations = 1;
+
+    [MethodImpl(MethodImplOptions.NoInlining)]
+    private static bool Bench(bool verbose = false)
+    {
+        int n = 16;
+        int maxDepth = Math.Max(minDepth + 2, n);
+        int stretchDepth = maxDepth + 1;
+        int t = 0;
+
+        int check = (TreeNode.bottomUpTree(0, stretchDepth)).itemCheck();
+        if (verbose)
+        {
+            Console.WriteLine("stretch tree of depth {0}\t check: {1}", stretchDepth, check);
+        }
+        t += check;
+
+        TreeNode longLivedTree = TreeNode.bottomUpTree(0, maxDepth);
+
+        for (int depth = minDepth; depth <= maxDepth; depth += 2)
+        {
+            int iterations = 1 << (maxDepth - depth + minDepth);
+
+            check = 0;
+            for (int i = 1; i <= iterations; i++)
+            {
+                check += (TreeNode.bottomUpTree(i, depth)).itemCheck();
+                check += (TreeNode.bottomUpTree(-i, depth)).itemCheck();
+            }
+
+            if (verbose)
+            {
+                Console.WriteLine("{0}\t trees of depth {1}\t check: {2}",
+                    iterations * 2, depth, check);
+            }
+
+            t += check;
+        }
+
+        if (verbose)
+        {
+            Console.WriteLine("long lived tree of depth {0}\t check: {1}",
+                maxDepth, longLivedTree.itemCheck());
+        }
+
+        t += check;
+
+        return (t == -174785);
+    }
+
+    private class TreeNode
+    {
+        private TreeNode left, right;
+        private int item;
+
+        private TreeNode(int item)
+        {
+            this.item = item;
+        }
+
+        internal static TreeNode bottomUpTree(int item, int depth)
+        {
+            TreeNode t;
+            ChildTreeNodes(out t, item, depth - 1);
+            return t;
+        }
+
+        static void ChildTreeNodes(out TreeNode node, int item, int depth)
+        {
+            node = new TreeNode(item);
+            if ( depth > 0 )
+            {
+                ChildTreeNodes(out node.left, 2 * item - 1, depth - 1);
+                ChildTreeNodes(out node.right, 2 * item, depth - 1);
+            }
+        }
+
+        internal int itemCheck()
+        {
+            if (right == null) return item;
+            else return item + left.itemCheck() - right.itemCheck();
+        }
+    }
+
+    [Benchmark]
+    public static void Test()
+    {
+        foreach (var iteration in Benchmark.Iterations)
+        {
+            using (iteration.StartMeasurement())
+            {
+                for (int i = 0; i < Iterations; i++)
+                {
+                    Bench();
+                }
+            }
+        }
+    }
+
+    private static bool TestBase()
+    {
+        bool result = true;
+        for (int i = 0; i < Iterations; i++)
+        {
+            result &= Bench(true);
+        }
+        return result;
+    }
+
+    public static int Main()
+    {
+        bool result = TestBase();
+        return (result ? 100 : -1);
+    }
+}
+}
diff --git a/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csproj b/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csproj
index d970a78c23..257a1d8466 100644
--- a/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csproj
+++ b/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csproj
@@ -20,6 +20,8 @@
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
   </PropertyGroup>
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+  </PropertyGroup>
+  <PropertyGroup>
     <DebugType>pdbonly</DebugType>
     <Optimize>true</Optimize>
   </PropertyGroup>
diff --git a/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees3.csproj b/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees3.csproj
new file mode 100644
index 0000000000..169e33d322
--- /dev/null
+++ b/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees3.csproj
@@ -0,0 +1,46 @@
+<?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>
+    <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\11.0\UITestExtensionPackages</ReferencePath>
+    <SolutionDir Condition="$(SolutionDir) == '' Or $(SolutionDir) == '*Undefined*'">..\..\</SolutionDir>
+    <NuGetPackageImportStamp>7a9bfb7d</NuGetPackageImportStamp>
+    <NuGetTargetMoniker>.NETStandard,Version=v1.4</NuGetTargetMoniker>
+    <GCStressIncompatible>true</GCStressIncompatible>
+  </PropertyGroup>
+  <!-- Default configurations to help VS understand the configurations -->
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+  </PropertyGroup>
+  <PropertyGroup>
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+  </PropertyGroup>
+  <ItemGroup>
+    <CodeAnalysisDependentAssemblyPaths Condition=" '$(VS100COMNTOOLS)' != '' " Include="$(VS100COMNTOOLS)..\IDE\PrivateAssemblies">
+      <Visible>False</Visible>
+    </CodeAnalysisDependentAssemblyPaths>
+  </ItemGroup>
+  <ItemGroup>
+    <Service Include="{82A7F48D-3B50-4B1E-B82E-3ADA8210C358}" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="binarytrees.csharp3.cs" />
+  </ItemGroup>
+  <PropertyGroup>
+    <ProjectJson>$(JitPackagesConfigFileDirectory)benchmark\project.json</ProjectJson>
+    <ProjectLockJson>$(JitPackagesConfigFileDirectory)benchmark\project.lock.json</ProjectLockJson>
+  </PropertyGroup>
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.targets))\dir.targets" />
+  <PropertyGroup Condition=" '$(MsBuildProjectDirOverride)' != '' ">
+  </PropertyGroup>
+</Project>