[LLVMdev] Naryreassociate vs reassociate
Daniel Berlin
dberlin at dberlin.org
Tue May 5 14:00:09 PDT 2015
On Tue, May 5, 2015 at 1:09 PM, Jingyue Wu <jingyue at google.com> wrote:
>
>
> On Tue, May 5, 2015 at 10:31 AM, Daniel Berlin <dberlin at dberlin.org> wrote:
>>
>> On Tue, May 5, 2015 at 10:20 AM, Jingyue Wu <jingyue at google.com> wrote:
>> > Hi Daniel,
>> >
>> > I presume you mean, instead of assigning function arguments distinct
>> > ranks
>> > (http://llvm.org/docs/doxygen/html/Reassociate_8cpp_source.html#l00282),
>> > we
>> > should group function arguments in favor of existing pairings.
>>
>> Existing = pairings reassociate already chose before
>> *not*
>> existing = pairings that already exist in the source IR
>>
>> Given that, we should probably group everything in favor of existing
>> pairings when possible.
>
>
> Makes sense.
>
>>
>>
>>
>> > You are not
>> > suggesting discarding the entire ranking system, right?
>>
>> The only three cases that should matter hugely are constants,
>> arguments, and non-movable instructions.
>>
>> The rest should hopefully already end up with consistent decisions.
>> If not, we have larger problems.
>>
>>
>> > I'll look into how that works on my benchmarks. AFAIK, we encountered
>> > some
>> > cases that seem beyond the fix you suggested. These cases involve
>> > constants,
>> > and I attached one reduced example in
>> > https://llvm.org/bugs/show_bug.cgi?id=22357.
>> >
>>
>> > void foo(int a, int b, int c, int *x, int *y) {
>> > *x = (a + b);
>> > *y = (a + 2) + b;
>> > }
>> >
>> > Reassociate assigns constants a lower rank than variables, which
>> > prevents
>> > Reassociate from transforming the above example to
>> >
>> > *x = a + b;
>> > *y = (a + b) + 2;
>> >
>>
>> This is a variant of the problem above, except you are getting ranks
>> 0, 1, 2 vs 1, 2
>
>
> The key difference is that constants are designed to be lowest ranked, and
> then the current reassociation algorithm always groups the constant 2 with
> other variables. Looks like your new solution will favor existing pairings
> regardless of the ranks. Then, it should be able to solve the a+b+2 case
> nicely.
So, right now, it rewrites it in optimally bad order to have this
happen. Because it puts highest ranked values first, it is guaranteed
that it will end up putting them not next to each other.
This is because in the ops == 2 case, it places the first two into the
same expression
In the ops > 2 case, it'll place the first two into different expressions.
So if you have
a+c
and
a+b+c
You are essentially guaranteed it will never put a and c next to each
other in both cases, unless a and c are the lowest ranked elements.
For the moment, i reversed the sort order, and we reassign ranks so
that things that it has processed before should end up next to each
other.
Because the sort is stable, you are only guaranteed they will end up
in the same expression, not necessarily ordered exactly the same way
they were last time.
This is fixable, but probably not worth it.
The patch is not perfect (and it is only lightly tested), but i'd love
to see how it goes.
Some issues
1. Because i reversed the sort order, it may do worse in other cases.
I can fix the sort order reversal by changing how we assign ranks slightly.
Basically, when we look for ops to pair with, we reassign the ranks to
be greater than the maximum rank for that bb (so it doesn't conflict
with anything).
2. It will only pair it the same way as the immediately last time it
paired it. I doubt there is anything much better unless you spend the
time you do in naryreassociate.
Honestly, after staring at this long enough, i'm pretty convinced we
should take an approach similar to naryreassociate's underpinnings in
reassociate.
In particular, i think we should deliberately unbalance the tree if we
can guarantee it will expose a redundancy (IE it will be an expression
we know is computed by one of our dominators).
This logic can be incorporated pretty easily into reassociate
-------------- next part --------------
diff --git a/lib/Transforms/Scalar/Reassociate.cpp b/lib/Transforms/Scalar/Reassociate.cpp
index b677523..787c29a 100644
--- a/lib/Transforms/Scalar/Reassociate.cpp
+++ b/lib/Transforms/Scalar/Reassociate.cpp
@@ -54,7 +54,7 @@ namespace {
ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {}
};
inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) {
- return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start.
+ return LHS.Rank < RHS.Rank; // Sort so that lowest rank goes to start.
}
}
@@ -159,6 +159,9 @@ namespace {
namespace {
class Reassociate : public FunctionPass {
DenseMap<BasicBlock*, unsigned> RankMap;
+ DenseMap<BasicBlock*, unsigned> MaxRankMap;
+ unsigned MaxArgRank;
+ DenseMap<AssertingVH<Value>, Value *> LastPairingMap;
DenseMap<AssertingVH<Value>, unsigned> ValueRankMap;
SetVector<AssertingVH<Instruction> > RedoInsts;
bool MadeChange;
@@ -284,7 +287,8 @@ void Reassociate::BuildRankMap(Function &F) {
ValueRankMap[&*I] = ++i;
DEBUG(dbgs() << "Calculated Rank[" << I->getName() << "] = " << i << "\n");
}
-
+ MaxArgRank = i;
+
ReversePostOrderTraversal<Function*> RPOT(&F);
for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
E = RPOT.end(); I != E; ++I) {
@@ -297,6 +301,7 @@ void Reassociate::BuildRankMap(Function &F) {
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
if (isUnmovableInstruction(I))
ValueRankMap[&*I] = ++BBRank;
+ MaxRankMap[BB] = BBRank;
}
}
@@ -787,6 +792,8 @@ void Reassociate::RewriteExprTree(BinaryOperator *I,
Value *NewRHS = Ops[i+1].Op;
Value *OldLHS = Op->getOperand(0);
Value *OldRHS = Op->getOperand(1);
+ LastPairingMap[NewLHS] = NewRHS;
+ LastPairingMap[NewRHS] = NewLHS;
if (NewLHS == OldLHS && NewRHS == OldRHS)
// Nothing changed, leave it alone.
@@ -818,7 +825,6 @@ void Reassociate::RewriteExprTree(BinaryOperator *I,
Op->setOperand(1, NewRHS);
}
DEBUG(dbgs() << "TO: " << *Op << '\n');
-
ExpressionChanged = Op;
MadeChange = true;
++NumChanged;
@@ -843,6 +849,8 @@ void Reassociate::RewriteExprTree(BinaryOperator *I,
Op->setOperand(1, NewRHS);
ExpressionChanged = Op;
}
+ LastPairingMap[NewRHS] = Op->getOperand(0);
+ LastPairingMap[Op->getOperand(0)] = NewRHS;
DEBUG(dbgs() << "TO: " << *Op << '\n');
MadeChange = true;
++NumChanged;
@@ -2166,6 +2174,35 @@ void Reassociate::ReassociateExpression(BinaryOperator *I) {
// operand information.
SmallVector<RepeatedValue, 8> Tree;
MadeChange |= LinearizeExprTree(I, Tree);
+
+ // Change the ranks of the operands to be next to the ones they paired with
+ // before
+ SmallPtrSet<Value*, 8> OpSet;
+ for (auto &Val : Tree)
+ OpSet.insert(Val.first);
+ SmallPtrSet<Value*, 8> Processed;
+ // Walk through our ops, seeing if we need to change rank numbers
+ for (auto &Op : Tree) {
+ if (Processed.count(Op.first))
+ continue;
+ Value *LastPairedWith = LastPairingMap.lookup(Op.first);
+ if (!LastPairedWith || OpSet.count(LastPairedWith) == 0)
+ continue;
+ // Put them next to each other by ran
+ if (Instruction *I = dyn_cast<Instruction>(Op.first)){
+ auto &MaxRank = MaxRankMap[I->getParent()];
+ ++MaxRank;
+ ValueRankMap[Op.first] = MaxRank;
+ ValueRankMap[LastPairedWith] = MaxRank;
+ } else {
+ ++MaxArgRank;
+ ValueRankMap[Op.first] = MaxArgRank;
+ ValueRankMap[LastPairedWith] = MaxArgRank;
+ }
+ Processed.insert(Op.first);
+ Processed.insert(LastPairedWith);
+ }
+
SmallVector<ValueEntry, 8> Ops;
Ops.reserve(Tree.size());
for (unsigned i = 0, e = Tree.size(); i != e; ++i) {
@@ -2180,8 +2217,8 @@ void Reassociate::ReassociateExpression(BinaryOperator *I) {
// the operands and their ranks, sort the operands by their rank. Use a
// stable_sort so that values with equal ranks will have their relative
// positions maintained (and so the compiler is deterministic). Note that
- // this sorts so that the highest ranking values end up at the beginning of
- // the vector.
+ // this sorts so that the lowest ranking values and least frequent values end
+ // up at the beginning of the vector.
std::stable_sort(Ops.begin(), Ops.end());
// Now that we have the expression tree in a convenient
@@ -2275,6 +2312,7 @@ bool Reassociate::runOnFunction(Function &F) {
// We are done with the rank map.
RankMap.clear();
ValueRankMap.clear();
-
+ MaxRankMap.clear();
+ LastPairingMap.clear();
return MadeChange;
}
More information about the llvm-dev
mailing list