Reassociate.cpp

        // and if this is not an inner node of a multiply tree.
        if (isReassociableOp(BI->getOperand(1), Instruction::Mul) &&
            (!BI->hasOneUse() ||
             !isReassociableOp(BI->use_back(), Instruction::Mul))) {
          BI = LowerNegateToMultiply(BI, ValueRankMap);
          MadeChange = true;
        }
      }
    }

    // If this instruction is a commutative binary operator, process it.
    if (!BI->isAssociative()) continue;
    BinaryOperator *I = cast<BinaryOperator>(BI);

    // If this is an interior node of a reassociable tree, ignore it until we
    // get to the root of the tree, to avoid N^2 analysis.
    if (I->hasOneUse() && isReassociableOp(I->use_back(), I->getOpcode()))
      continue;

    // If this is an add tree that is used by a sub instruction, ignore it 
    // until we process the subtract.
    if (I->hasOneUse() && I->getOpcode() == Instruction::Add &&
        cast<Instruction>(I->use_back())->getOpcode() == Instruction::Sub)
      continue;

    ReassociateExpression(I);
  }
}

Value *Reassociate::ReassociateExpression(BinaryOperator *I) {
  
  // First, walk the expression tree, linearizing the tree, collecting the
  // operand information.
  SmallVector<ValueEntry, 8> Ops;
  LinearizeExprTree(I, Ops);
  
  DEBUG(dbgs() << "RAIn:\t"; PrintOps(I, Ops); dbgs() << '\n');
  
  // Now that we have linearized the tree to a list and have gathered all of
  // 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.
  std::stable_sort(Ops.begin(), Ops.end());
  
  // OptimizeExpression - Now that we have the expression tree in a convenient
  // sorted form, optimize it globally if possible.
  if (Value *V = OptimizeExpression(I, Ops)) {
    // This expression tree simplified to something that isn't a tree,
    // eliminate it.
    DEBUG(dbgs() << "Reassoc to scalar: " << *V << '\n');
    I->replaceAllUsesWith(V);
    RemoveDeadBinaryOp(I);
    ++NumAnnihil;
    return V;
  }
  
  // We want to sink immediates as deeply as possible except in the case where
  // this is a multiply tree used only by an add, and the immediate is a -1.
  // In this case we reassociate to put the negation on the outside so that we
  // can fold the negation into the add: (-X)*Y + Z -> Z-X*Y
  if (I->getOpcode() == Instruction::Mul && I->hasOneUse() &&
      cast<Instruction>(I->use_back())->getOpcode() == Instruction::Add &&
      isa<ConstantInt>(Ops.back().Op) &&
      cast<ConstantInt>(Ops.back().Op)->isAllOnesValue()) {
    ValueEntry Tmp = Ops.pop_back_val();
    Ops.insert(Ops.begin(), Tmp);
  }
  
  DEBUG(dbgs() << "RAOut:\t"; PrintOps(I, Ops); dbgs() << '\n');
  
  if (Ops.size() == 1) {
    // This expression tree simplified to something that isn't a tree,
    // eliminate it.
    I->replaceAllUsesWith(Ops[0].Op);
    RemoveDeadBinaryOp(I);
    return Ops[0].Op;
  }
  
  // Now that we ordered and optimized the expressions, splat them back into
  // the expression tree, removing any unneeded nodes.
  RewriteExprTree(I, Ops);
  return I;
}


bool Reassociate::runOnFunction(Function &F) {
  // Recalculate the rank map for F
  BuildRankMap(F);

  MadeChange = false;
  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
    ReassociateBB(FI);

  // We are done with the rank map.
  RankMap.clear();
  ValueRankMap.clear();
  return MadeChange;
}