Memory-dependence prediction (MDP) increases instruction-level parallelism (ILP) by allowing load instructions to be issued even when addresses in the store queue are unknown. The predictor determines whether a load will alias with a prior store, delaying issue when a dependence is predicted. Speculative memory bypassing (SMB) further enhances ILP by short-circuiting a predicted dependence to forward the value written by a store to a load that is predicted to depend on it, without their addresses necessarily being known. This breaks data dependencies on the load and store addresses, allowing loads to obtain their values much earlier than they normally would. To obtain benefits, dependencies must be predicted with high accuracy. Furthermore, the benefits are skewed, with false negatives being more costly for performance than false positives for MDP, since the former requires squashing when the misprediction is identified, whereas the latter only delays the issue of independent loads. For SMB, on the other hand, false positives are very costly, as they require squashing, whereas false negatives have little impact in the presence of an accurate memory dependence predictor. Due to these differing requirements, the designs of predictors for these mechanisms have diverged. In this paper, we propose Mascot, a novel predictor capable of performing both MDP and SMB. MASCOT is inspired by the TAGE predictor, widely used in branch prediction. Although TAGE has proven effective as a universal predictor structure, we demonstrate how prior TAGE-based MDP or SMB predictors suffer from inaccuracy due to not learning patterns of non-dependence. By learning the context for dependencies as well as non-dependencies, Mascot achieves sufficiently low false negatives and false positives to perform MDP and SMB, while at the same time uses less space than existing designs that only perform MDP or SMB. Our simulation results show that for SPEC CPU 2017, MAscot used for MDP alone yields an IPC gain of ${0. 4 \%}$ over the previous state-of-the-art predictor, on average, at the same size. When used for both MDP and SMB, it yields an increase in IPC of 1.9% on average, with peak gains of 26%. A compacted version of Mascot, Mascot-opt, achieves similar numbers within 0.1% while using just 10.1 KiB of space.

Memory dependence prediction is a fundamental technique to increase instruction- and memory-level parallelism in out-of-order processors, which are crucial for high performance. However, over the years, the performance gap of state-of-the-art memory dependence predictors with respect to an ideal predictor has grown due to the increase of the pipeline width, reaching up to 6% for modern architectures. State-of-the-art predictors brace context sensitivity, however, not-well-adjusted history lengths lead to loss of accuracy and high storage requirements. This work proposes PHAST, a novel context-sensitive memory dependence predictor that identifies for each load the minimum history length necessary to provide precise predictions. Our key observation is that for each load, it suffices to identify the youngest conflicting store and the path between them. This observation is proven empirically using an unlimited budget version of PHAST, which performs close to an ideal predictor with a 0.47% gap. Through cycle-accurate simulation of the SPEC CPU 2017 suite, we show that a 14.5KB implementation of PHAST falls 1.50% behind an ideal predictor. Compared to the top-performing state-of-the-art predictors, PHAST achieves average speedups of 5.05% (up to 39.7%), 1.29% (up to 22.0%), and 3.04% (up to 38.2%) with respect to an 18.5KB StoreSets, a 19KB NoSQ, and a 38.6 MDP-TAGE, respectively. This stems from a considerable misprediction reduction, ranging between 62.5% and 70.0%, on average.