Microsoft Technology Licensing, LLC

Other

James J Radigan

Ian Michael Bearman

David N Cutler

Karim Taji Farouki

Gor Nishanov

Scott D Mosier

Ian H Carmichael

Amit Jayant Sabne

Lawrence B Sullivan

Algorithms, examples, and related technology for automatic vectorization of a particular class of loops is described. The loops, denoted 'CMMSR loops', operate to find an extremum and also utilize an index denoting the position of the extremum in an array or other multi-element input. CMMSR loops are identified in a language translator by matching a specified template or having a specified set of parsing results, or both. Generated vectorization code includes, for example, code to compute candidates for the extremum, code to select the same instance of the extremum as a scalar execution when the input contains multiple instances, and wind-down code to compute an index expression based on the selected instance of the extremum. Vectorizations may execute on SIMD hardware or other vector processors.

Vectorizing conditional min-max sequence reduction loops

As a memory usage optimization, a compiler identifies coroutines whose activation frames can be allocated on a caller's stack instead of allocating the frame on the heap. For example, when the compiler determines that a coroutine C's life cannot extend beyond the life of the routine R that first calls the coroutine C, the compiler generates code to allocate the activation frame for C on the stack of R, instead of generating code to allocate C's frame from heap memory. In some cases, as another optimization, code for coroutine C is also inlined with code for the routine R that calls C. Coroutine activation frame content variations and layout variations are also described.

Compiler optimization of coroutines

A compiler-created cache contains target addresses of multiple indirect routine call sites. Ordinals assigned to indirect routine call sites are used with hardcoded offsets into the cache. Ordinals may be computed using a routine counter and an indirect call site counter. At runtime a target address of an indirect routine call site is compared to an entry in the cache using the hardcoded offset for efficiency. If the target address matches the cache entry, then a redundant call is avoided; otherwise, the call is not redundant, and the cache is updated. The call tested for redundancy may be a security check for malware, or a computationally expensive routine which calculates a return value without any side effects. Stack pointer validity may be checked. The cache may be guarded with code for trustworthy computing. Tail merging may be performed.

Compiler caching for runtime routine redundancy tracking

A generated grouped representation of existing source code can define regions of the existing source code. A set of the regions that can run in parallel can be identified based on the grouped representation. The grouped representation can be converted into a modified representation, such as modified source code or a modified intermediate compiler representation, which can be configured to be resolved or executed to self-schedule the set of regions to run in parallel as a set of tasks. Additionally, the source code can include one or more exception handling routines, and user input can be received to identify in one or more lambda expressions one or more regions of the source code to be run in parallel as one or more tasks.

Generation of parallel code representations

In an exemplary media implementation, one or more electronically-accessible media include electronically-executable instructions that utilize an application programming interface, the application programming interface facilitating creation of callback-type dynamic function tables; each callback-type dynamic function table including a begin address, an end address, and a callback function, each callback-type dynamic function table corresponding to a code heap that stores code for multiple functions in a runtime environment; wherein interaction between the runtime environment and an operating system is precipitated upon calling the callback function to acquire exception handling and/or unwind information. In another exemplary media implementation, one or more electronically-accessible media include at least part of an operating system that is configured to request from a runtime environment exception handling and/or unwinding information for functions that are managed by the runtime environment.

Operating system managing a linked list of callback dynamic function tables for acquiring exception handling information from a runtime environment

A compiler that forms an intermediate representation of a program using a flow graph with less than all possible edges used to model asynchronous transfers within the program. The flow graph is formed in multiple phases. In one phase, the flow graph is formed without modeling asynchronous transfers. In later phases, representations of the effects of the asynchronous transfers are selectively added. As part of the later phases, edges modeling a possible asynchronous transfer are added to the flow graph following definitions in protected regions of variables that are live outside the protected region. A modified definition of live-ness of a variable is used to incorporate use of the variable in any region, including the protected region, following an asynchronous transfer. Edges from the protected region are also added to the model if the only use of the defined variable is in a handler.

Software tool with modeling of asynchronous program flow

Tool for processing software programs using modified live-ness definition

The construction of Static Single Assignment form (SSA) is used as a dynamic conflict graph so that while constructing SSA in linear time, the program being analyzed is simultaneously register allocated. When allocating a register for the symbol, the conflict set is examined so that the register chosen for the symbol is not used by a symbol in the conflict set. When a symbol is register-allocated, the symbol is added to all the conflict set of all live symbols. A live symbol is determined by keeping two counters, called herein a use counter and a use threshold counter. Both counters are initialized when a definition of a symbol is encountered in a block. Both counters are incremented when a use of the symbol is encountered when traversing a block in a depth-first downward traversal. The use count is decremented when a use is detected when traversing the block in an upward traversal. A symbol is live when the use count is less than the use count threshold and the use count is greater than zero when a register is allocated. The register-allocated symbol is added to the conflict set of all live symbols.

System and method for register allocation using SSA construction

A developer's system compiles a source-language program by parsing it into an intermediate language (IL) program that is independent of the architecture or resources of any particular processor. This system generates a set of machine independent annotations that record attributes and structure of the IL program such as variable definitions and uses. The annotations are in the form of a unique graph structure. Further annotations are used to associate the machine specific optimization information with each of many different microprocessors. The IL program and all the annotations are distributed to multiple user systems having mutually different virtual machines that translate the IL program into object language for their respective different processors. Optimizers in the virtual machines select graph edges based on the machine specific annotations to generate an optimized object program. The translators are table-driven. Entities in the IL program are keyed to entries in a replaceable table in each virtual machine.

Growing community of inventors

Sammamish, WA, United States of America

James J Radigan