Changed to a left leaning red black tree implementation

This change takes the algorithm as presented in Robert
Sedgewick's paper
[Left-leaning Red-Black Trees](http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf)
and implements it in C#.  The implementation is a fairly
direct transliteration of the paper.

The code is integrated with the previous code's harness, but
little else remains.

If the DEBUG property is set, then it checks the invariants
of the tree are re-established after each insert and delete.

Fixed parent pointers becoming corrupt

In the rotation case, the grandparent of x is not correctly updated, and
thus the parent pointer can point outside the tree.

Merge pull request #3243 from LLITCHEV/structDesc-clone

Added code to clone the structDesc member of GT_CALL.

Merge pull request #3135 from CarolEidt/x86VirtualStubDirect

Enable Virtual Stub calls that are direct for x86

Added code to clone the structDesc member of GT_CALL.

Adds code to clone the structDesc member of GT_CALL. It modifies the
importer to get the structDesc directly in this field, instead of using a
separate local and eliminates the obsolete SetRegisterReturningStructState
method of GenTreeCall.

Fixes 3239.

Merge pull request #3237 from AndyAyersMS/InlineRefactor4b

Inline refactoring: capture failing observation for non-candidates

Inline refactoring: capture failing observation for non-candidates

Refactor the InlineResult to take a `GenTreeCall` instead of artifacts
derived from the call. Use this to decorate the call (in DEBUG) if
an inline fails with the observation that lead to the failure. Move
this constructor out of the header since we now need it to invoke
methods on types that are header-opaque.

Try and pick this reason up later on when non-candidate call sites are
encountered during inlining.

Introduce a second constructor for the pre-jit use case, where we are
evaulating a method to see if we can mark it as never inline to save
work in any subsequent compilation. Put this into the cpp file too for
symmetry.

Type the backing field in GenTreeCall as unsigned to avoid creating
more deeply entangled include circularities. Happy to reconsider if
this seems ill-advised.

Reword a few more uses of inlinee to callee (similarly inliner to
caller). Make `inlIsValidObservation` globally visible and enable
a prior commented-out assert.

Enable Virtual Stub calls that are direct for x86

On x86, direct virtual stub calls must be done with a relative address, NOT through a register.

Merge pull request #3229 from AndyAyersMS/InlineRefactor4a

Inline refactoring: add candidate observations

Merge pull request #3219 from adityamandaleeka/twowaypipe_cleanup

Clean up Unix twowaypipe code

Merge pull request #3222 from richardlford/testswithrefs0216

Port desktop tests that had references

Merge pull request #3231 from ellismg/add-back-push-triggers

Add back push triggers

Merge pull request #3230 from jkotas/jitee-cleanup

Delete NetCF quirk and MDIL generation support from RyuJIT and JIT-EE interface

Delete 'do not port' test, add non-windows exclusions

Add back push triggers

Do {debug|checked|release} builds for all platforms on push. Upstack
projects (e.g CoreFX) take some of these as inputs and we use the
results in building out the badge links.

For the jobs which have flow's, just build the folow (which will trigger
the non flow builds).

Delete unused files

Delete MDIL generation support from JIT-EE interface

Merge pull request #3224 from gkhanna79/UpdateNugetPkg

Update CoreCLR Nuget package

Delete NetCF quirks from RyuJIT

Inline refactoring: add candidate observations

Add candidate observations and update the InlineResult to hold
onto the observation rather than the reason string.

Merge pull request #3196 from AndyAyersMS/InlineRefactor4

Inline refactoring: header cleanup and some renaming

Update CoreCLR Nuget package version to be 1.0.2.

Merge pull request #3191 from manu-silicon/absolute_path

Fix absolute path on Linux

Fix typo in genXplatEventing.py.

Use pal.h directly in Unix twowaypipe code and remove windefs.h.

Port desktop tests that had references

This change ports desktop tests that had references to dlls.
It also fixes some of the dll project files.
In addition there are some additional tests that were not
previously ported (but that do not reference dlls).

There are 4 tests that are excluded because of issue #3216.

Merge pull request #3218 from sergiy-k/niimageloading

Change MAPMapPEFile to use ExecutableAllcator instead of mmap to reserve VA

Merge pull request #3220 from dotnet-bot/from-tfs

Merge changes from TFS

port fix for pad ratio

[tfs-changeset: 1576135]

Fix ildasm to be run without specifying the full path

Using the fixed version of GetEntrypointExecutableAbsolutePath when the
program name on the command line does not reflect an actual file on disk
(case when a program is launched by finding it in the PATH). This should fix
issue#3190.

Change MAPMapPEFile to use ExecutableAllcator instead of mmap to reserve VA

This change modifies the MAPMapPEFile in PAL to use ExecutableAllcator
instead of mmap in order to reserve VA for managed executable images. This
allows all NI images to be located near each other and close to the
coreclr library, which also allows the runtime to generate code that is
more efficient (by avoiding usage of jump stubs).

It also fixes an issue (https://github.com/dotnet/cli/issues/652) where
CLI fails with OutOfMemoryException which turned out to be related to
loading NI files. Due to a certain allocation pattern, mmap can place an
NI file at a region of virtual address space that does not have any free
memory around the NI images. As a result, when the runtime needs to
allocate memory for jump stubs for the image it cannot find any available
memory near the image and fails with OutOfMemoryException.

Fix GetEntrypointExecutableAbsolutePath on Linux

Although PR#1818 was supposed to implement this for Linux, only the MacOS X
implementation was correct. We are now using `readlink' on Linux to get
the path of the current running executable.

Merge pull request #3215 from jkotas/arm-floatargs

Save/restore floating point arguments in asm macros on Linux arm and arm64

Remove PAL_unlink.

Save/restore floating point arguments in transition block on arm and arm64

The transition block prolog/epilog macros were not correctly saving and restoring the floating point arguments on arm and arm64 on Unix.

Merge pull request #3213 from rahku/fixarm64

Fix arm64 build break

Merge pull request #3189 from krytarowski/netbsd-support-49

Enforce compiler version of alloca(3) on NetBSD

Merge pull request #3212 from dotnet-bot/from-tfs

Merge changes from TFS

Merge pull request #3166 from sejongoh/add_linux_corefx_testing

Enable linux corefx testing

Fix arm64 build break

Fix NetBSD build issue: Use compiler version of alloca(3) when possible

The documentation of alloca(3) says:

     o   The alloca() function should be supplied by the compiler because the
         compiler is allowed to make assumptions about the stack and frame
         pointers.  The libc alloca() implementation cannot account for those
         assumptions.  While there is a machine dependent implementation of
         alloca() in libc, its use is discouraged and in most cases it will
         not work.  Using this implementation will produce linker warnings.

This is true for CoreCLR - alloca(3) was breaking 30 PAL tests.

Enforce on this operating system a compiler version.

Thanks Jan Kotas (Microsoft) for inspiration what may go wrong.
Thanks Jan Vorli (Microsoft) for useful suggestions in order to fix it.

Merge pull request #3211 from gregg-miskelly/OSXAttachFix

Fix debugger attach to process on OSX

Option for Enforcing Intrinsic Expansion

Currently intrinsic is disabled under MIN_OPT while being enabled under OPT.
There is no way to enforce intrinsic expansion where non-intrinsic (call) path is not yet implemented.
This adds an optional output boolean argument to getIntrinsicID that tells JIT whether to enforce intrinsic expansion.
If JIT cannot expand intrinsic for such case, fatal error occurs.
There is no functional change the argument is default to false.

[tfs-changeset: 1575973]

Merge pull request #3177 from krytarowski/netbsd-support-47

Fix build issue on NetBSD: Make RPATH optional and user-settable

Merge pull request #3205 from AndyAyersMS/FixBenchFProjFiles

Remove IlasmRoundTrip from these project files

Fix debugger attach to process on OSX

Attaching to processes on OSX was broken with the way the .NET CLI is installing CoreCLR. The issue is that the vmmap executable that dbgshim is using will, by default, truncate paths. This caused it to be unable to find the real path to DBI.

Fix: pass the '-wide' argument to vmmap

Inline refactoring: header cleanup and some renaming

Move inlining classes and related bits of code into inline.h.
Rename `JitInlineResult` to `InlineResult` and `InlInlineHints` to
`InlineHints`.

Merge pull request #3203 from AndyAyersMS/FixJitMemoryUsage

Fix issue with excessive memory use by debug and checked jits

Merge pull request #3173 from mikedn/ssadef-dup

Remove duplicate calls to GetPerSsaData

Merge pull request #3176 from mikedn/topref

Avoid unnecessary copies of AllSuccessorIter and LocationInfo

Remove IlasmRoundTrip from these project files

We test ilasm/ildasm separately, so no reason to round trip when
building these benchmarks.

Closes #3202.

Merge pull request #3187 from manu-silicon/ildasm

Fix ildasm when ran against CoreFX assemblies like System.Runtime

Fix issue with excessive memory use by debug and checked jits

In #3051 the jit started calling `eeGetClassFullName` for both
caller and callee handles even when dumping was disabled, passed
this information to the logging messages where previously the caller
and callee were identified via other context, and prepared the full
name dump artifacts for all inline decisions rather than the selective
cases handled previously.

This change caused excessive memory use in some tests.

This change makes the calls to `eeGetClassFullName` conditional on
whether dumping is enabled, and does not require these calls for logging
messages.

Fix invalid usage of pointer and SZSTRING_REMAINING_SIZE macro

When manipulating strings, the string destination buffer and the argument
of SZSTRING_REMAINING_SIZE should be the same otherwise buffer
overflows will occur.
Changed DumpHexbytes to start from the provided pointer and not finding
out how much was printed so far in the szString buffer.

Merge pull request #3200 from dotnet-bot/from-tfs

Merge changes from TFS

Fix build issue on NetBSD: Make RPATH optional and user-settable

The `$ORIGIN` linker feature isn't supported on NetBSD.

All RPATH is done via `pkgsrc` on all supported platforms, allow to override it.
pkgsrc will set CORECLR_SET_RPATH:BOOL=OFF and specify manually needed options.

Fix Init to return False when not being able to load executable

Merge pull request #3195 from janvorli/fix-invalid-gcvalue

Fix INVALIDGCVALUE on Unix

Merge pull request #3167 from mikem8361/tracing

Fix tracing lib problems in multiple PALs. Issue #3164.

Finish fixing VSO #190301. DACRaiseException need some STATIC_ contracts.

[tfs-changeset: 1575640]

Merge pull request #3193 from richardlford/addtestlibs0216

Add libraries for tests that reference them.

Fix INVALIDGCVALUE on Unix

The INVALIDGCVALUE value loaded into the R11 in the JIT_WriteBarrier_Debug
and JIT_ByRefWriteBarrier is sign extended to 0xFFFFFFFFCCCCCCCD instead of
being the 0x00000000CCCCCCCD.
It was introduced during the early days of CoreCLR porting when I have
misread the error message that I was getting from Clang when compiling
mov R11, 0xCCCCCCCD and didn't know yet that loading 64 bit number requires
using the movabs mnemonics.

Make dll project files build-only.

Dll project files need extra properties to avoid being run as tests.

Merge pull request #3124 from AndyAyersMS/InlineRefactor3

Inline refactoring: start untangling observation and policy

Merge pull request #3185 from janvorli/fix-exception-severity

Fix missing exception corruption severity setting

Add libraries for tests that reference them.

This change adds dynamic link libraries that are referenced
by other tests.

Avoid unnecessary copies of AllSuccessorIter,  LocationInfo  and VNDefFunc2Arg

ArrayStack<T>::Top() returns a copy rather than a reference like typical C++ containers do. For large Ts like AllSuccessorIterator and LocationInfo this results in a lot of code bloat and unncessary copying. Add a T& TopRef() function to avoid such copying.

Fix missing exception corruption severity setting

This change fixes missing exception corruption severity for exceptions
that were thrown by native code but didn't pass through any managed
frames yet.

We have seen assert in the RaiseTheException function when an exception
thrown from native code is caught in native code without passing through
any managed frames and then it is being thrown in a wrapper TargetInvocationException.

Inline refactoring: start untangling observation and policy

Create set of observations that can be made during inlining. These
are implemented as a set of static tables plus some helper methods.
Each observation has an enum name, a type, a description string,
an impact, and a target.

For now most observations are about blocking issues and are classified
as having FATAL impact. There are a handful of INFORMATIONAL and
PERFORMANCE observations but they're not widely used yet.

This change also updates the bulk of the jit code to report
observations to the JitInlineResult instead of directly requesting
changes to the JitInlineResult state. Over on the JitInlineResult side,
the current legacy policy is implemented and fails fast if any blocking
observation is made. For now, any any FATAL impact observation must be
made via `noteFatal`, and all other observations be made via `note`.

As with the previous refactorings, this change tries not to alter
any code generation. There are a few cases where observations that
are made solely about the callee are now targeted that way instead of
being targeted at callsites. For instance a method that is marked by
COMPLUS_JitNoInline will never be inlined. This can sometimes lead to
localized code diffs, since the jit creates slightly different IR for a
call to an inline candidate than a call to a non-candidate, and is not
always able to undo this later if inlining fails. However the number of
diffs should be small. Will verify diffs further before merging. There
are no inlining changes crossgenning mscorlib.

Some of the message strings associated with inlining failures have
changed. The messages use `caller` and `callee` to describe the two
methods involved, and `callsite` for the instance in question, and
deprecate `inlinee`. These message strings can be seen in the jit
dumps and logs and are reported back to the VM where they presumably
make their way into other diagnostic reporting streams.

Subsequent work will re-examine the FATAL observations and likely
reclassify a number of them to have less dramatic immediate impact.
Subsequent work will also begin extracting the policy into a separate
class to lay the groundwork for supporting alternate policies while
still being able to fall back to the legacy policy.

Merge pull request #3179 from JohnChen0/crossgen-fprintf

Fix fprintf in crossgen

Merge pull request #2992 from steveharter/FixSanitizerClrStartup

Clang sanitizer: remove unaligned address check

Enable linux corefx testing

Merge pull request #3183 from janvorli/fix-unwound-funclet-stack-reporting

Fix unwound funclet GC stack reporting on Unix

Merge pull request #3157 from benaadams/QueueUserWorkItemCallback

Slimmer QueueUserWorkItemCallback

Fix unwound funclet GC stack reporting on Unix

This change fixes a problem with reporting object on stack for GC when
GC scan is performed right after a funclet is unwound during exception handling.
In such case, the parent of the funclet should report live object references,
but it was not doing so on Unix.
On Unix, the unwound funclet is detected in a different way than on Windows due
to the fact that the stack frames of the funclet are already reclaimed, while on
Windows, they are still there.
When we detect the unwound funclet on Unix, we set state of the stack walker so
that it behaves in the same way as on Windows. But we were missing one state
variable that makes the parent report the references instead of the funclet,
the m_fDidFuncletReportGCReferences.

Merge pull request #3170 from krytarowski/netbsd-support-44

Prefer BSD uuid over libuuid

Merge pull request #3149 from krytarowski/netbsd-support-41

Fix build issue on NetBSD: Include <time.h> for time(3) in gc.cpp

Merge pull request #3171 from krytarowski/netbsd-support-45

Add more CMake sugar for NetBSD

Merge pull request #3160 from josteink/master

Make the coreclr build-process support rtags

Merge pull request #3175 from krytarowski/netbsd-support-46

Fix build issue on NetBSD: Remove unneeded -nostdinc++ flag

Fix fprintf in crossgen

CrossGen configures its stdout to allow only Unicode output functions.
Add a wrapper to fprintf to allow it to work inside crossgen.

Slimmer QueueUserWorkItemCallback

Prefer BSD uuid over libuuid

This fixes recent NetBSDbuild breakage:
../libcoreclrpal.a(miscpalapi.cpp.o): In function `CoCreateGuid':
/tmp/pkgsrc-tmp/wip/coreclr-git/work/coreclr/src/pal/src/misc/miscpalapi.cpp:356: undefined reference to `uuid_generate_random'
clang-3.9: error: linker command failed with exit code 1 (use -v to see invocation)

No need to link against libuuid.

Add detection of BSD-styl <uuid.h>.
Few Linux distros ship with custom <uuid.h> and they aren't compatibile.

Merge pull request #3162 from dotnet-bot/from-tfs

Merge changes from TFS

Fix build issue on NetBSD: Remove unneeded -nostdinc++ flag

This flag isn't recognized by clang on NetBSD:
clang-3.9: warning: argument unused during compilation: '-nostdinc++'

$ pkg_info |grep -E 'lldb|llvm|clang'
llvm-3.9.0nb20160213 Low Level Virtual Machine compiler infrastructure
clang-3.9.0nb20160213 C language family frontend for LLVM
lldb-3.9.0nb20160213 next generation, high-performance debugger

$ uname -a
NetBSD chieftec 7.99.26 NetBSD 7.99.26 (GENERIC) #0: Wed Feb 10 21:58:18 UTC 2016
root@chieftec:/tmp/netbsd-tmp/sys/arch/amd64/compile/GENERIC amd64

This flag was disabled also for Darwin in #125 by @jkotas

Fix build issue on NetBSD: Add time(3) to PAL

Otherwise it triggers linker warnings.

/tmp/pkgsrc-tmp/wip/coreclr-git/work/coreclr/src/gc/gc.cpp:33869:
warning: warning: reference to compatibility time(); include <time.h> for correct reference

$ uname -a
NetBSD chieftec 7.99.25 NetBSD 7.99.25 (GENERIC) #0: Fri Dec 25 20:51:06 UTC 2015  root@chieftec:/tmp/netbsd-tmp/sys/arch/amd64/compile/GENERIC amd64

Remove duplicate calls to GetPerSsaData

The code is too complex for the C++ compiler to figure out that it is duplicated and the generated code contains a second call to ExpandArray::EnsureCoversInd for what is otherwise just a trivial assignment.

Merge pull request #3172 from RussKeldorph/redisable

Re-disable tests failing due to #2728

Re-disable tests failing due to #2728

Add more CMake sugar for NetBSD

This resolves 'gen-dactable-rva.sh does not print to dactablerva.h' #3168

This fixes issue with g_dacTable unavailable in libcoreclr.so.

This patch assumes GNU ld(1) on NetBSD

Thanks to Bruce Mitchener @waywardmonkeys for pointing out ld(1) nits.

Make the build-process support rtags

Rtags depends on cmake to export its build commands in order to index
the codebase.

Adding this flag makes cmake do that.

Merge pull request #3161 from richardlford/restoredllnames0212

Restore original dll names, use Define constants.

Fix tracing lib problems in multiple PALs. Issue #3164.

Moved the tracepointprovider loading in miscpalapi.cpp to separate library that
is only linked by libcoreclr.so.

Merge pull request #3145 from erozenfeld/PreserveCastVN

Preserve value numbers when discarding a cast.

Fix hfa_interop to omit ".dll" from DLLName

For interoperability cross platform, the DLL name given to the
DllImport attribute should not include the suffix since
dynamic link libraries use a different suffix on different
systems.

Merge pull request #3159 from mikem8361/security

Change the transport pipe and runtime startup semaphores permissions

Clang sanitizer: remove unaligned address check

Fix build issue #788907: crossgen /createpdb not working

[tfs-changeset: 1575079]

Restore original dll names, use Define constants.

This changes set has no functional change, rather it cleans
up some aspects of a previous port.

When the hfa dlls were originally ported it was not known that
C# #defines could be used in the tests, so source files that
use #if were expanded to multiple source files with the preprocessing
being done manually. This changes goes back to using the original
files with appropriate define constants in the project files.

In addition, when these dlls were ported abbreviated names were
used. This change restores the dll names to the originals.

Merge pull request #3153 from briansull/issue_2816_v2

Fix issues with passing 16-byte structs on Arm64