High-Level Synthesis (HLS) tools automatically transform a high-level specification of a circuit into a low-level RTL description.Traditionally, HLS tools have operated on sequential code, howeverin recent years there has been a drive to synthesize multi-threadedcode. A major challenge facing HLS tools in this context is how toautomatically partition memory amongst parallel threads to fullyexploit the bandwidth available on an FPGA device and avoid mem-ory contention. Current automatic memory partitioning techniqueshave inefficient arbitration due to conservative assumptions regard-ing which threads may access a given memory bank. In this paper,we address this problem through formal verification techniques,permitting a less conservative, yet provably correct circuit to begenerated. We perform a static analysis on the code to determinewhich memory banks are shared by which threads. This analysisenables us to optimize the arbitration efficiency of the generatedcircuit. We apply our approach to the LegUp HLS tool and showthat for a set of typical application benchmarks we can achieve upto 87% area savings, and 39% execution time improvement, withlittle additional compilation time.