Skip to content
This repository was archived by the owner on Jan 23, 2023. It is now read-only.

JIT: Transform X % C == 0 to X & (C-1) == 0 #25744

Closed
EgorBo wants to merge 9 commits into from
Closed

JIT: Transform X % C == 0 to X & (C-1) == 0 #25744

Changes from all commits
Commits
Show all changes
9 commits
Select commit Hold shift + click to select a range
2459d77
X % C == 0 can be transformed to X & (C-1) == 0 if C is a power of two
EgorBo Jul 17, 2019
37cacba
make sure op1->op1 is integer
EgorBo Jul 17, 2019
1e578c5
Address feedback
EgorBo Jul 17, 2019
93e4c24
change to GT_UMOD
EgorBo Jul 17, 2019
0e53872
Add CM_EQ_OP label
EgorBo Jul 17, 2019
8ec24d9
fix formatting issues
EgorBo Jul 17, 2019
3ec39e0
fix formatting issues
EgorBo Jul 17, 2019
a9c3508
Merge remote-tracking branch 'dotnet/master' into jit-opt-mod
EgorBo Aug 9, 2019
6fc00a5
Fix CM_EQ_OP
EgorBo Aug 9, 2019
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
26 changes: 26 additions & 0 deletions src/jit/morph.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -12278,6 +12278,8 @@ GenTree* Compiler::fgMorphSmpOp(GenTree* tree, MorphAddrContext* mac)
}
break;

CM_EQ_OP:

case GT_EQ:
case GT_NE:

Expand Down Expand Up @@ -12326,6 +12328,25 @@ GenTree* Compiler::fgMorphSmpOp(GenTree* tree, MorphAddrContext* mac)
}
}

// Transform X MOD C == 0 to X UMOD C == 0 if C is a power of two
// then lowering will be able to transform it to X & (C-1) == 0
if (op2->IsIntegralConst(0))
{
op1 = tree->AsOp()->gtGetOp1();
if (op1->OperIs(GT_MOD))
{
if (varTypeIsIntegralOrI(op1->AsOp()->gtGetOp1()->gtType) &&
(op1->AsOp()->gtGetOp2()->IsIntegralConst()))
{
ssize_t divider = op1->AsOp()->gtGetOp2()->AsIntCon()->IconValue();
if (isPow2(divider))
{
op1->SetOper(GT_UMOD);
}
}
}
}

//
// Here we look for the following tree
//
Expand Down Expand Up @@ -12745,6 +12766,11 @@ GenTree* Compiler::fgMorphSmpOp(GenTree* tree, MorphAddrContext* mac)
oper = (oper == GT_LE) ? GT_EQ : GT_NE;
tree->SetOper(oper, GenTree::PRESERVE_VN);
tree->gtFlags &= ~GTF_UNSIGNED;

if (op1->OperIs(GT_MOD))
Copy link

@sandreenko sandreenko Oct 21, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@EgorBo I was trying to review that PR and lost the track of the changes, the first part Transform X MOD C == 0 to X UMOD C == 0 looks clear, but why were this label and goto added?

and it is really scary for me to have a back edge in a function like fgMorphSmpOp especially for 500 lines length.

Copy link
Member Author

@EgorBo EgorBo Oct 21, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@sandreenko I wanted to handle X % C != 0 but couldn't just visit GT_NE node - Roslyn emits cgt.un (GT_GT) and morph converts it back to GT_NE but doesn't visit GT_NE after. So I have three options to fix the != 0 case:

  1. Handle unsigned GT_GT node instead of GT_NE
  2. Convert GT_GT to GT_NE early in the importer
  3. goto GT_NE (current)

Copy link

@sandreenko sandreenko Oct 23, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Won't it be better to call fgMorphSmpOp recursively here?

Copy link
Member Author

@EgorBo EgorBo Oct 23, 2019 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@sandreenko will try, but I think there will be a few regressions

{
goto CM_EQ_OP;
}
}
}
}
Expand Down