Let $M$ be a (possibly non-orientable) compact 3-manifold
with (possibly empty) boundary consisting of tori and Klein
bottles. Let $X\subset\partial M$ be a trivalent graph such
that $\partial M\setminus X$ is a union of one disc for each
component of $\partial M$. Building on previous work of
Matveev, we define for the pair $(M,X)$ a complexity
$c(M,X)\in\mathbb{N}$ and show that, when $M$ is closed,
irreducible and $\mathbb{P}^2$-irreducible, $c(M,\emptyset)$
is the minimal number of tetrahedra in a triangulation of
$M$. Moreover $c$ is additive under connected sum, and, given
any $n\geqslant 0$, there are only finitely many irreducible
and $\mathbb{P}^2$-irreducible closed manifolds having
complexity up to $n$. We prove that every irreducible and
$\mathbb{P}^2$-irreducible pair $(M,X)$ has a finite splitting
along tori and Klein bottles into pairs having the same
properties, and complexity is additive on this splitting. As
opposed to the JSJ decomposition, our splitting is not
canonical, but it involves much easier blocks than all Seifert
and simple manifolds. In particular, most Seifert and
hyperbolic manifolds appear to have non-trivial splitting. In
addition, a given set of blocks can be combined to give only a
finite number of pairs $(M,X)$. Our splitting theorem provides
the theoretical background for an algorithm which classifies
3-manifolds of any given complexity. This algorithm has been
already implemented and proved effective in the orientable
case for complexity up to 9.