An efficient static analysis algorithm to detect redundant memory operations

As memory system performance becomes an increasingly dominant factor in overall system performance, it is im-portant to optimize programs for memory related opera-tions. This paper concerns static analysis to detect redun-dant memory operations and enable other compiler trans-formations to remove such redundant operations. We present an extended global value numbering algorithm to detect redundant memory operations. The key of the new algorithm is a novel SSA-based representation for memory state which allows accurate reasoning about memory state. Using this representation, the algorithm can trace values through memory operations to detect equivalence in the same way that it traces them through register-based scalar operations. Thus it discovers both redundancy involving scalar values and redundancy involving memory operations. The redundancy relation detected by the algorithm can then be used by traditional redundancy elimination transforma-tions to remove those redundant operations. Experiments using a suite of realistic applications demon-strate the algorithm is powerful and fast. In practice, it has essentially linear time complexity. 1