https://gcc.gnu.org/bugzilla/show_bug.cgi?id=126664
Bug ID: 126664
Summary: unswitch does not update probabilities of unswitched
condition
Product: gcc
Version: 17.0
Status: UNCONFIRMED
Keywords: missed-optimization
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: arsen at gcc dot gnu.org
Target Milestone: ---
it seems that, after unswitching a loop, GCC does not update the edge
probabilities on the condition it hoists.
this is very visible in the following testcase:
using size_t = __SIZE_TYPE__;
using int32_t = __INT32_TYPE__;
#define ZERO 0.0f
#define QUARTER 0.25f
#define HALF 0.5f
#define ONE 1.0f
#define TWO 2.0f
#define FOUR 4.0f
#define CNSTNT 45.0f
// Energy evaluation parameters
#define HBTYPE_F 70
#define HBTYPE_E 69
#define HARDNESS 38.0f
#define NPNPDIST 5.5f
#define NPPDIST 1.0f
static constexpr auto FloatMax = 3.40282346638528859811704183484516925e+38F;
constexpr int PPWI = 1;
struct // __attribute__((__packed__))
Atom {
float x, y, z;
int32_t type;
};
struct // __attribute__((__packed__))
FFParams {
int32_t hbtype;
float radius;
float hphb;
float elsc;
};
void fasten_main(size_t group, size_t ntypes, size_t nposes, size_t natlig,
size_t natpro, //
const Atom *protein, const Atom *ligand,
//
const float *transforms_0, const float
*transforms_1, const float *transforms_2, //
const float *transforms_3, const float
*transforms_4, const float *transforms_5, //
const FFParams *forcefield, float *energies, int il
//
) {
float transform[3][4][PPWI];
float etot[PPWI];
#pragma omp simd
for (int l = 0; l < PPWI; l++) {
int ix = group * PPWI + l;
// Compute transformation matrix
const float sx = __builtin_sinf(transforms_0[ix]);
const float cx = __builtin_cosf(transforms_0[ix]);
const float sy = __builtin_sinf(transforms_1[ix]);
const float cy = __builtin_cosf(transforms_1[ix]);
const float sz = __builtin_sinf(transforms_2[ix]);
const float cz = __builtin_cosf(transforms_2[ix]);
transform[0][0][l] = cy * cz;
transform[0][1][l] = sx * sy * cz - cx * sz;
transform[0][2][l] = cx * sy * cz + sx * sz;
transform[0][3][l] = transforms_3[ix];
transform[1][0][l] = cy * sz;
transform[1][1][l] = sx * sy * sz + cx * cz;
transform[1][2][l] = cx * sy * sz - sx * cz;
transform[1][3][l] = transforms_4[ix];
transform[2][0][l] = -sy;
transform[2][1][l] = sx * cy;
transform[2][2][l] = cx * cy;
transform[2][3][l] = transforms_5[ix];
etot[l] = 0.f;
}
const Atom l_atom = ligand[il];
const FFParams l_params = forcefield[l_atom.type];
const int lhphb_ltz = l_params.hphb < 0.f;
const int lhphb_gtz = l_params.hphb > 0.f;
// Transform ligand atom
float lpos_x[PPWI], lpos_y[PPWI], lpos_z[PPWI];
#pragma omp simd
for (int l = 0; l < PPWI; l++) {
lpos_x[l] = transform[0][3][l] + l_atom.x * transform[0][0][l] +
l_atom.y * transform[0][1][l] +
l_atom.z * transform[0][2][l];
lpos_y[l] = transform[1][3][l] + l_atom.x * transform[1][0][l] +
l_atom.y * transform[1][1][l] +
l_atom.z * transform[1][2][l];
lpos_z[l] = transform[2][3][l] + l_atom.x * transform[2][0][l] +
l_atom.y * transform[2][1][l] +
l_atom.z * transform[2][2][l];
}
// Loop over protein atoms
for (int ip = 0; ip < natpro; ip++) {
// Load protein atom data
const Atom p_atom = protein[ip];
const FFParams p_params = forcefield[p_atom.type];
const float radij = p_params.radius + l_params.radius;
const float r_radij = ONE / radij;
const float elcdst = (p_params.hbtype == HBTYPE_F && l_params.hbtype
== HBTYPE_F) ? FOUR : TWO;
const float elcdst1 = (p_params.hbtype == HBTYPE_F && l_params.hbtype
== HBTYPE_F) ? QUARTER : HALF;
const int type_E = ((p_params.hbtype == HBTYPE_E || l_params.hbtype
== HBTYPE_E));
const int phphb_ltz = p_params.hphb < 0.f;
const int phphb_gtz = p_params.hphb > 0.f;
const int phphb_nz = p_params.hphb != 0.f;
const float p_hphb = p_params.hphb * (phphb_ltz && lhphb_gtz ? -ONE :
ONE);
const float l_hphb = l_params.hphb * (phphb_gtz && lhphb_ltz ? -ONE :
ONE);
const float distdslv = (phphb_ltz ? (lhphb_ltz ? NPNPDIST : NPPDIST)
: (lhphb_ltz ? NPPDIST : -FloatMax));
const float r_distdslv = ONE / distdslv;
const float chrg_init = l_params.elsc * p_params.elsc;
const float dslv_init = p_hphb + l_hphb;
#pragma omp simd
for (int l = 0; l < PPWI; l++) {
// Calculate distance between atoms
const float x = lpos_x[l] - p_atom.x;
const float y = lpos_y[l] - p_atom.y;
const float z = lpos_z[l] - p_atom.z;
const float distij = __builtin_sqrtf(x * x + y * y + z * z);
// Calculate the sum of the sphere radii
const float distbb = distij - radij;
const int zone1 = (distbb < ZERO);
// Calculate steric energy
// Calculate formal and dipole charge interactions
float chrg_e = chrg_init * ((zone1 ? ONE : (ONE - distbb *
elcdst1)) * (distbb < elcdst ? ONE : ZERO));
float neg_chrg_e = -__builtin_fabs(chrg_e);
chrg_e = type_E ? neg_chrg_e : chrg_e;
// Calculate the two cases for Nonpolar-Polar repulsive
interactions
float coeff = (ONE - (distbb * r_distdslv));
float dslv_e = dslv_init * ((distbb < distdslv && phphb_nz) ? ONE :
0.f);
dslv_e *= (zone1 ? ONE : coeff);
etot[l] += ((ONE - (distij * r_radij)) * (zone1 ? TWO * HARDNESS :
0.f)) + (chrg_e * CNSTNT) + dslv_e;
}
}
// Write result
#pragma omp simd
for (int l = 0; l < PPWI; l++) {
energies[group * PPWI + l] = etot[l] * HALF;
}
}
... which was isolated from miniBUDEs src/omp/fasten.hpp.
looking at the loopinit dump, BB16 has a condition l_params$hphb_187 < 0.0
which GCC estimates is extremely unlikely to be true (0%):
<bb 16> [local count: 186884766]:
if (l_params$hphb_187 < 0.0)
goto <bb 17>; [0.00%]
else
goto <bb 36>; [100.00%]
...
<bb 17> [local count: 0]:
this is not an unfair assumption, the following hold when BB16 is reached:
_41 = l_params$hphb_187 < 0.0 (set in BB3, outside of the loop)
_72 = p_params$hphb_198 > 0.0 (set in BB11, dominates BB16)
_73 = _41 & _72 (ditto)
!_73 (BB11->BB13, pred. of BB16)
therefore, at most on of _41 or _72 is true
!(p_params$hphb_198 < 0.0) (BB13->BB16)
therefore, p_params$hphb_198 >= 0.0
therefore, for _41 to hold, !_72 must hold,
so, !_72 & (p_params$hphb_198 >= 0.0) must hold
so, !(p_params$hphb_198 > 0.0) & (p_params$hphb_198 >= 0.0) must
hold
so, p_params$hphb_198 = 0.0 must hold
so, _41 is unlikely
... or at least I guess that's how it deduced this (I'm not sure - I haven't
looked into how probabilities are estimated before, and this specific estimate
only comes into existence after dom2 so it goes through quite a few rounds of
updates between profile_estimate and then)
however, when GCC chooses to unswitch this loop based on the condition in BB16,
it copies the branch probabilities from above, so we end up with (in the
unswitch dump):
<bb 3> [local count: 59055799]:
[...]
_41 = l_params$hphb_187 < 0.0;
[...]
if (l_params$hphb_187 < 0.0)
goto <bb 76>; [0.00%]
else
goto <bb 77>; [100.00%]
<bb 77> [local count: 59055799]:
<bb 41> [local count: 536870910]:
[...]
<bb 76> [local count: 0]:
<bb 4> [local count: 0]:
[...]
... but the only condition that holds upon entry to bb 3 is natpro != 0:
<bb 2> [local count: 66354830]:
if (natpro_122(D) != 0)
goto <bb 3>; [89.00%]
else
goto <bb 30>; [11.00%]
<bb 3> [local count: 59055799]:
[...]
... thus, those probabilities are very wrong.
this results in the loop on BB4 not getting vectorized, leading to a slowdown
of 9x on the bm1 benchmark on GCN (though this issue exists on x86 also;
measured by making the vectorizer optimize even !optimize_loop_nest_for_speed_p
loop; I haven't measured the impact on x86 yet though)
in general, I don't see reasons to assume that an unswitched condition retains
pre-unswitch probabilities
