  We examine verification of concurrent programs under the total store ordering
(TSO) semantics used by the x86 architecture. In our model, threads manipulate
variables over infinite domains and they can check whether variables are
related for a range of relations. We show that, in general, the control state
reachability problem is undecidable. This result is derived through a reduction
from the state reachability problem of lossy channel systems with data (which
is known to be undecidable). In the light of this undecidability, we turn our
attention to a more tractable variant of the reachability problem.
Specifically, we study context bounded runs, which provide an
under-approximation of the program behavior by limiting the possible
interactions between processes. A run consists of a number of contexts, with
each context representing a sequence of steps where a only single designated
thread is active. We prove that the control state reachability problem under
bounded context switching is PSPACE complete.
