• zdjones's avatar
    cmd/compile: make prove use poset to check non-negatives · ddef1578
    zdjones authored
    Prove currently fails to remove bounds checks of the form:
    
    if i >= 0 {              // hint that i is non-negative
        for i < len(data) {  // i becomes Phi in the loop SSA
            _ = data[i]      // data[Phi]; bounds check!!
    	i++
        }
    }
    
    addIndVarRestrictions fails to identify that the loop induction
    variable, (Phi), is non-negative. As a result, the restrictions,
    i <= Phi < len(data), are only added for the signed domain. When
    testing the bounds check, addBranchRestrictions is similarly unable
    to infer that Phi is non-negative. As a result, the restriction,
    Phi >= len(data), is only added/tested for the unsigned domain.
    
    This CL changes the isNonNegative method to utilise the factTable's
    partially ordered set (poset). It also adds field factTable.zero to
    allow isNonNegative to query the poset using the zero(0) constant
    found or created early in prove.
    
    Fixes #28956
    
    Change-Id: I792f886c652eeaa339b0d57d5faefbf5922fe44f
    Reviewed-on: https://go-review.googlesource.com/c/go/+/161437
    Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
    TryBot-Result: Gobot Gobot <gobot@golang.org>
    Reviewed-by: default avatarGiovanni Bajo <rasky@develer.com>
    ddef1578
prove.go 34.7 KB