\section{Introduction}
\label{Se:intro}
Software developers have traditionally benefited from advances in computer
architecture, which, over multiple decades, has provided a steady increase in
the computing resources available to applications.
However, the immense heat dissipation and power usage that results from
ramping up the clock frequency has (temporarily) stalled this process.

To continue to provide software developers with increased computing resources,
computer architecture has focused on thread-level parallelism. This is evident
by the myriad of chip multiprocessors (CMP) in today's commodity PCs. A CMP
consists of multiple processing cores on one die. Many of today's laptops now
include dual-core processors. There are predictions that the next generation
of processors will be 4 or 8-way CMPs.

The CMP trend in computer architecture implies that software
developers will need to write concurrent programs to take advantage of
the increased processing power. In the past, the synchronization
primitives used to write concurrent programs have traditionally been
locks, semaphores, and condition variables. These primitives are both
error-prone and do not scale to many threads of
execution. Furthermore, it has been shown that this is neither
composable nor effective for large data structures, such as hashtables
\cite{DBLP:conf/ppopp/HarrisMPH05}.

The difficulties of lock-based programming led to research in programming with
{\em transactions}. In abstract terms, a transaction is a sequence of events
that appear to happen atomically. The idea of using transactions was borrowed
from the database community. Traditional database transactions support ACID
(Atomicity, Consistency, Isolation, and Durability) semantics. To avoid
confusion, we will refer to transactions used in programs as software
transactions.

A {\em software transaction} consists of a sequence of instructions executed
by one thread, whose side effects appear to happen at once. Software
transactions give programmers a declarative way of expressing
synchronization---the programmer will specify \emph{what} program statements
are to be executed atomically and not how the atomic execution is implemented.
Due to the volatile nature of memory, software transactions only concern
themselves with the first three principles of database transactions, namely
ACI.

Software transactions strive to facilitate the writing of correct
highly-concurrent programs. By the abstract specification of atomic sections,
performance of multithreaded programs can be improved by executing software
transactions that operate on disjoint data in parallel. Lock-based critical
sections, on the other hand, are serialized if they are protected by the same
lock regardless of the data actually accessed. Additionally, programmers can
leave the implementation of atomic critical sections to the underlying system.


There have been many research proposals, from both the architecture and
programming languages communities, investigating {\em transactional memory}
(TM) systems to support software transactions. 
These include TM systems that are implemented
completely in software (STM) \cite{shavit:sw-trans-mem:podc:1995,
DBLP:conf/oopsla/HarrisF03, DBLP:conf/icfp/RingenburgG05,
herlihy:sw-trans-mem:podc:2003}, in hardware (HTM)
\cite{herlihy:transactional:isca:1993, hammond:tcc:isca:2004,
ananian:utm:hpca:2005, rajwar:vtm:isca:2005,moore:logtm:hpca:2006},
and implementations that have various aspects implemented in hardware
and software (HyTM)
\cite{damron:hytm:asplos:2006,kumar:hybrid-tm:ppopp:2006}.
TM systems attempt to execute software transactions concurrently. They
typically enforce atomicity and isolation by stalling or aborting software
transactions that conflict.  A {\em conflict} occurs when two transactions
access the same data concurrently, and one of them is a write.


While software transactions present a step forward in the evolution of
concurrent programming, programmers using software transactions must
still reason about program correctness and performance. Bugs may result from
accesses to shared data structures that are inconsistently protected by
software transactions.  A program's performance can suffer if concurrency is
limited by conflicting transactions. The problem of transaction conflicts can
be exacerbated by transactional memory systems that detect conflicts at a
coarse granularity. For example, many HTM's detect conflicts between
concurrent transactions using the cache coherence mechanism. To conserve
hardware resources, these systems typically detect conflicts at the
granularity of a cache line.  In such systems, concurrent accesses to
different words in the same cache line by two different transactions can cause
a \emph{false conflict} (i.e., an unnecessary serialization of transactions
that is due solely to the heuristic nature of a platform's conflict-detection
mechanism---see \defref{falseconflict}). False conflicts can cause significant
performance loss on HTMs \cite{moore:logtm:hpca:2006}.

To address these problems, we introduce three interprocedural dataflow
analyses. The first analysis, XRef, is a static analysis that annotates the
fields of each record type\footnote{We use the term ``record'' to emphasize
that the analysis is language independent. A record type corresponds to a C
\texttt{struct} or to a class in an object-oriented language.
}
in the program with the static transactions (\defref{staticxact}) in which
they are referenced. These (automatically inferred) annotations are important
for analysis tools whose focus includes transactional software. That is, the
results of XRef analysis form a basic building block on which other analyses
can be built. We demonstrate this capability by implementing with our other
two interprocedural analyses, XOrder and XProtect, on top of XRef.


We address false conflicts through XOrder analysis. Specifically, the goal of
XOrder analysis is to reduce false conflicts among concurrent software
transactions. XOrder analysis targets TM systems systems that detect conflicts
at a coarse granularity. Using a detailed simulator of an HTM system, XOrder
analysis more than doubled the performance for one benchmark.

XProtect is a consistency analysis. It detects when the fields of a shared
record are not consistently protected by a software transaction.
Inconsistencies can result in unintended program behaviors and data races.

We are (essentially) inferring annotations for the fields of  record types. This
allows us to ignore thread interleavings, and hence we need only union the
results from a sequential analysis of each thread. One way to accomplish this
is to model the program with a ``supermain'' function that
nondeterministically  branches to the entry point of each thread, including
the {\tt main} function.

The contributions of this paper are:
\begin{itemize}
\renewcommand{\labelitemi}{$\bullet$}
\item
XRef, a new software analysis that annotates the fields of a record with the
static transactions in which they are accessed.

\item XOrder, a software optimization that determines an optimized memory layout 
for the fields of a record. We measured speedups of up to 2.8.

\item
XProtect, a safety analysis that detects when a shared data structure is not
consistently protected by a software transaction.

\item
Our analyses are able to analyze existing lock-based programs in a
transactional setting.

\end{itemize}


The remainder of the paper is organized as follows:
\sectref{Model} specifies the programming model.
\sectref{DynamicTransaction} and 
\sectref{StaticTransactions} introduce the notion of a dynamic transaction and
static transaction, respectively. \sectref{XRef} presents XRef.
\sectref{XOrder} and \sectref{XProtect} present our additional program
analyses XOrder and XProtect, respectively. \sectref{Related} discusses
related work.
