We prove that supports of non-symmetric Macdonald polynomials are $M$-convex. As a consequence, we resolve a 2019 conjecture of Monical, Tokcan, and Yong that they have the saturated Newton polytope property. As a corollary we show that affine Demazure characters of type $\mathrm{GL}$ have M-convex supports and therefore the saturated Newton polytope property answering a 2022 open question of Besson and Hong. By their results, we then find that certain affine analogs of Bruhat interval polytopes in type $\mathrm{GL}$ are generalized permutahedra. To prove these results, we find a novel interpretation of the Haglund--Haiman--Loehr formula for non-symmetric Macdonald polynomials in terms of colorings of Dyck graphs.