bool AfterLegalize;
bool Fast;
- // Create a dummy node (which is not added to allnodes), that adds a reference
- // to the root node, preventing it from being deleted, and tracking any
- // changes of the root.
- HandleSDNode Dummy;
-
// Worklist of all of the nodes that need to be simplified.
- SmallVector<SDNode*, 8> WorkList;
-
- // The current position of our iteration through the allnodes list.
- SelectionDAG::allnodes_iterator CurNode;
+ std::vector<SDNode*> WorkList;
// AA - Used for DAG load/store alias analysis.
AliasAnalysis &AA;
- /// AdvanceCurNode - Update CurNode to point to the next node to process.
- ///
- void AdvanceCurNode() {
- // We start at the end of the list and work towards the front. Setting
- // CurNode to DAG.allnodes_end() indicates that we're done.
- if (CurNode == DAG.allnodes_begin())
- CurNode = DAG.allnodes_end();
- else
- --CurNode;
- }
-
/// AddUsersToWorkList - When an instruction is simplified, add all users of
/// the instruction to the work lists because they might get more simplified
/// now.
void removeFromWorkList(SDNode *N) {
WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), N),
WorkList.end());
- // If the next node we were planning to process is deleted,
- // skip past it.
- if (N == CurNode)
- AdvanceCurNode();
}
SDValue CombineTo(SDNode *N, const SDValue *To, unsigned NumTo,
// Visitation implementation - Implement dag node combining for different
// node types. The semantics are as follows:
// Return Value:
- // SDValue.getNode() == 0 - No change was made
- // SDValue.getNode() == N - N was replaced, is dead, and is already handled.
- // otherwise - N should be replaced by the returned Operand.
+ // SDValue.getNode() == 0 - No change was made
+ // SDValue.getNode() == N - N was replaced, is dead and has been handled.
+ // otherwise - N should be replaced by the returned Operand.
//
SDValue visitTokenFactor(SDNode *N);
SDValue visitMERGE_VALUES(SDNode *N);
TLI(D.getTargetLoweringInfo()),
AfterLegalize(false),
Fast(fast),
- Dummy(D.getRoot()),
AA(A) {}
/// Run - runs the dag combiner on all nodes in the work list
void Run(bool RunningAfterLegalize);
-
- /// ProcessNode - runs the dag combiner on a node
- void ProcessNode(SDNode *N);
};
}
// Main DAG Combiner implementation
//===----------------------------------------------------------------------===//
-void DAGCombiner::ProcessNode(SDNode *N) {
- // If N has no uses, it is dead. Make sure to revisit all N's operands once
- // N is deleted from the DAG, since they too may now be dead or may have a
- // reduced number of uses, allowing other xforms.
- if (N->use_empty() && N != &Dummy) {
- for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
- AddToWorkList(N->getOperand(i).getNode());
-
- DAG.DeleteNode(N);
- return;
- }
-
- SDValue RV = combine(N);
-
- if (RV.getNode() == 0)
- return;
-
- ++NodesCombined;
-
- // If we get back the same node we passed in, rather than a new node or
- // zero, we know that the node must have defined multiple values and
- // CombineTo was used. Since CombineTo takes care of the worklist
- // mechanics for us, we have no work to do in this case.
- if (RV.getNode() == N)
- return;
-
- assert(N->getOpcode() != ISD::DELETED_NODE &&
- RV.getNode()->getOpcode() != ISD::DELETED_NODE &&
- "Node was deleted but visit returned new node!");
-
- DOUT << "\nReplacing.3 "; DEBUG(N->dump(&DAG));
- DOUT << "\nWith: "; DEBUG(RV.getNode()->dump(&DAG));
- DOUT << '\n';
-
- if (N->getNumValues() == RV.getNode()->getNumValues())
- DAG.ReplaceAllUsesWith(N, RV.getNode());
- else {
- assert(N->getValueType(0) == RV.getValueType() &&
- N->getNumValues() == 1 && "Type mismatch");
- SDValue OpV = RV;
- DAG.ReplaceAllUsesWith(N, &OpV);
- }
-
- // Delete the old node.
- removeFromWorkList(N);
- DAG.DeleteNode(N);
-
- // Push the new node and any users onto the worklist
- AddToWorkList(RV.getNode());
- AddUsersToWorkList(RV.getNode());
-}
-
void DAGCombiner::Run(bool RunningAfterLegalize) {
// set the instance variable, so that the various visit routines may use it.
AfterLegalize = RunningAfterLegalize;
+ // Add all the dag nodes to the worklist.
+ WorkList.reserve(DAG.allnodes_size());
+ for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
+ E = DAG.allnodes_end(); I != E; ++I)
+ WorkList.push_back(I);
+
+ // Create a dummy node (which is not added to allnodes), that adds a reference
+ // to the root node, preventing it from being deleted, and tracking any
+ // changes of the root.
+ HandleSDNode Dummy(DAG.getRoot());
+
// The root of the dag may dangle to deleted nodes until the dag combiner is
// done. Set it to null to avoid confusion.
DAG.setRoot(SDValue());
- // Process all the original dag nodes. We process starting from the
- // end of the list and working forward, which is in roughly topological
- // order. Starting at the end and working forward means we won't
- // accidentally revisit nodes created during the dagcombine process.
- CurNode = prior(DAG.allnodes_end());
- do {
- SDNode *N = &*CurNode;
- AdvanceCurNode();
- ProcessNode(N);
- // Processing the node may have resulted in nodes being added to the
- // worklist, because the were newly created or because one of their
- // operands changed or some other reason they should be revisited.
- // While the worklist isn't empty, inspect the node on the end of it
- // and try and combine it.
- while (!WorkList.empty()) {
- SDNode *N = WorkList.back();
- WorkList.pop_back();
- if (N == CurNode)
- AdvanceCurNode();
- ProcessNode(N);
+ // while the worklist isn't empty, inspect the node on the end of it and
+ // try and combine it.
+ while (!WorkList.empty()) {
+ SDNode *N = WorkList.back();
+ WorkList.pop_back();
+
+ // If N has no uses, it is dead. Make sure to revisit all N's operands once
+ // N is deleted from the DAG, since they too may now be dead or may have a
+ // reduced number of uses, allowing other xforms.
+ if (N->use_empty() && N != &Dummy) {
+ for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
+ AddToWorkList(N->getOperand(i).getNode());
+
+ DAG.DeleteNode(N);
+ continue;
}
- } while (CurNode != DAG.allnodes_end());
-
+
+ SDValue RV = combine(N);
+
+ if (RV.getNode() == 0)
+ continue;
+
+ ++NodesCombined;
+
+ // If we get back the same node we passed in, rather than a new node or
+ // zero, we know that the node must have defined multiple values and
+ // CombineTo was used. Since CombineTo takes care of the worklist
+ // mechanics for us, we have no work to do in this case.
+ if (RV.getNode() == N)
+ continue;
+
+ assert(N->getOpcode() != ISD::DELETED_NODE &&
+ RV.getNode()->getOpcode() != ISD::DELETED_NODE &&
+ "Node was deleted but visit returned new node!");
+
+ DOUT << "\nReplacing.3 "; DEBUG(N->dump(&DAG));
+ DOUT << "\nWith: "; DEBUG(RV.getNode()->dump(&DAG));
+ DOUT << '\n';
+ WorkListRemover DeadNodes(*this);
+ if (N->getNumValues() == RV.getNode()->getNumValues())
+ DAG.ReplaceAllUsesWith(N, RV.getNode(), &DeadNodes);
+ else {
+ assert(N->getValueType(0) == RV.getValueType() &&
+ N->getNumValues() == 1 && "Type mismatch");
+ SDValue OpV = RV;
+ DAG.ReplaceAllUsesWith(N, &OpV, &DeadNodes);
+ }
+
+ // Push the new node and any users onto the worklist
+ AddToWorkList(RV.getNode());
+ AddUsersToWorkList(RV.getNode());
+
+ // Add any uses of the old node to the worklist in case this node is the
+ // last one that uses them. They may become dead after this node is
+ // deleted.
+ for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
+ AddToWorkList(N->getOperand(i).getNode());
+
+ // Nodes can be reintroduced into the worklist. Make sure we do not
+ // process a node that has been replaced.
+ removeFromWorkList(N);
+
+ // Finally, since the node is now dead, remove it from the graph.
+ DAG.DeleteNode(N);
+ }
+
// If the root changed (e.g. it was a dead load, update the root).
DAG.setRoot(Dummy.getValue());
}
N0.getNode()->hasOneUse()) {
Sh = N0; Y = N1;
} else if (N1.getOpcode() == ISD::SHL &&
- isa<ConstantSDNode>(N1.getOperand(1)) && N1.getNode()->hasOneUse()) {
+ isa<ConstantSDNode>(N1.getOperand(1)) &&
+ N1.getNode()->hasOneUse()) {
Sh = N1; Y = N0;
}
if (Sh.getNode()) {
if (ConstantSDNode *SUBC =
dyn_cast<ConstantSDNode>(LHSShiftAmt.getOperand(0))) {
if (SUBC->getAPIntValue() == OpSizeInBits) {
- if (HasROTL)
- return DAG.getNode(ISD::ROTL, VT, LHSShiftArg, LHSShiftAmt).getNode();
- else
+ if (HasROTR)
return DAG.getNode(ISD::ROTR, VT, LHSShiftArg, RHSShiftAmt).getNode();
+ else
+ return DAG.getNode(ISD::ROTL, VT, LHSShiftArg, LHSShiftAmt).getNode();
}
}
}
if (RExtOp0.getOpcode() == ISD::SUB &&
RExtOp0.getOperand(1) == LExtOp0) {
// fold (or (shl x, (*ext y)), (srl x, (*ext (sub 32, y)))) ->
- // (rotr x, y)
+ // (rotl x, y)
// fold (or (shl x, (*ext y)), (srl x, (*ext (sub 32, y)))) ->
- // (rotl x, (sub 32, y))
+ // (rotr x, (sub 32, y))
if (ConstantSDNode *SUBC = cast<ConstantSDNode>(RExtOp0.getOperand(0))) {
if (SUBC->getAPIntValue() == OpSizeInBits) {
- if (HasROTL)
- return DAG.getNode(ISD::ROTL, VT, LHSShiftArg, LHSShiftAmt).getNode();
- else
- return DAG.getNode(ISD::ROTR, VT, LHSShiftArg, RHSShiftAmt).getNode();
+ return DAG.getNode(HasROTL ? ISD::ROTL : ISD::ROTR, VT, LHSShiftArg,
+ HasROTL ? LHSShiftAmt : RHSShiftAmt).getNode();
}
}
} else if (LExtOp0.getOpcode() == ISD::SUB &&
RExtOp0 == LExtOp0.getOperand(1)) {
- // fold (or (shl x, (*ext (sub 32, y))), (srl x, (*ext r))) ->
- // (rotl x, y)
- // fold (or (shl x, (*ext (sub 32, y))), (srl x, (*ext r))) ->
- // (rotr x, (sub 32, y))
+ // fold (or (shl x, (*ext (sub 32, y))), (srl x, (*ext y))) ->
+ // (rotr x, y)
+ // fold (or (shl x, (*ext (sub 32, y))), (srl x, (*ext y))) ->
+ // (rotl x, (sub 32, y))
if (ConstantSDNode *SUBC = cast<ConstantSDNode>(LExtOp0.getOperand(0))) {
if (SUBC->getAPIntValue() == OpSizeInBits) {
- if (HasROTL)
- return DAG.getNode(ISD::ROTL, VT, LHSShiftArg, RHSShiftAmt).getNode();
- else
- return DAG.getNode(ISD::ROTL, VT, LHSShiftArg, LHSShiftAmt).getNode();
+ return DAG.getNode(HasROTR ? ISD::ROTR : ISD::ROTL, VT, LHSShiftArg,
+ HasROTR ? RHSShiftAmt : LHSShiftAmt).getNode();
}
}
}
}
// fold (not (zext (setcc x, y))) -> (zext (not (setcc x, y)))
if (N1C && N1C->getAPIntValue() == 1 && N0.getOpcode() == ISD::ZERO_EXTEND &&
- N0.getNode()->hasOneUse() && isSetCCEquivalent(N0.getOperand(0), LHS, RHS, CC)){
+ N0.getNode()->hasOneUse() &&
+ isSetCCEquivalent(N0.getOperand(0), LHS, RHS, CC)){
SDValue V = N0.getOperand(0);
V = DAG.getNode(ISD::XOR, V.getValueType(), V,
DAG.getConstant(1, V.getValueType()));
if (DAG.MaskedValueIsZero(SDValue(N, 0),
APInt::getAllOnesValue(VT.getSizeInBits())))
return DAG.getConstant(0, VT);
+ // fold (shl x, (trunc (and y, c))) -> (shl x, (and (trunc y), c))
+ // iff (trunc c) == c
+ if (N1.getOpcode() == ISD::TRUNCATE &&
+ N1.getOperand(0).getOpcode() == ISD::AND) {
+ SDValue N101 = N1.getOperand(0).getOperand(1);
+ ConstantSDNode *N101C = dyn_cast<ConstantSDNode>(N101);
+ if (N101C) {
+ MVT TruncVT = N1.getValueType();
+ unsigned TruncBitSize = TruncVT.getSizeInBits();
+ APInt ShAmt = N101C->getAPIntValue();
+ if (ShAmt.trunc(TruncBitSize).getZExtValue() == N101C->getValue()) {
+ SDValue N100 = N1.getOperand(0).getOperand(0);
+ return DAG.getNode(ISD::SHL, VT, N0,
+ DAG.getNode(ISD::AND, TruncVT,
+ DAG.getNode(ISD::TRUNCATE, TruncVT, N100),
+ DAG.getConstant(N101C->getValue(), TruncVT)));
+ }
+ }
+ }
+
if (N1C && SimplifyDemandedBits(SDValue(N, 0)))
return SDValue(N, 0);
// fold (shl (shl x, c1), c2) -> 0 or (shl x, c1+c2)
// If the shift is not a no-op (in which case this should be just a sign
// extend already), the truncated to type is legal, sign_extend is legal
- // on that type, and the the truncate to that type is both legal and free,
+ // on that type, and the the truncate to that type is both legal and free,
// perform the transform.
if (ShiftAmt &&
TLI.isOperationLegal(ISD::SIGN_EXTEND, TruncVT) &&
}
}
+ // fold (sra x, (trunc (and y, c))) -> (sra x, (and (trunc y), c))
+ // iff (trunc c) == c
+ if (N1.getOpcode() == ISD::TRUNCATE &&
+ N1.getOperand(0).getOpcode() == ISD::AND) {
+ SDValue N101 = N1.getOperand(0).getOperand(1);
+ ConstantSDNode *N101C = dyn_cast<ConstantSDNode>(N101);
+ if (N101C) {
+ MVT TruncVT = N1.getValueType();
+ unsigned TruncBitSize = TruncVT.getSizeInBits();
+ APInt ShAmt = N101C->getAPIntValue();
+ if (ShAmt.trunc(TruncBitSize).getZExtValue() == N101C->getValue()) {
+ SDValue N100 = N1.getOperand(0).getOperand(0);
+ return DAG.getNode(ISD::SRA, VT, N0,
+ DAG.getNode(ISD::AND, TruncVT,
+ DAG.getNode(ISD::TRUNCATE, TruncVT, N100),
+ DAG.getConstant(N101C->getValue(), TruncVT)));
+ }
+ }
+ }
+
// Simplify, based on bits shifted out of the LHS.
if (N1C && SimplifyDemandedBits(SDValue(N, 0)))
return SDValue(N, 0);
return DAG.getNode(ISD::XOR, VT, Op, DAG.getConstant(1, VT));
}
}
+
+ // fold (srl x, (trunc (and y, c))) -> (srl x, (and (trunc y), c))
+ // iff (trunc c) == c
+ if (N1.getOpcode() == ISD::TRUNCATE &&
+ N1.getOperand(0).getOpcode() == ISD::AND) {
+ SDValue N101 = N1.getOperand(0).getOperand(1);
+ ConstantSDNode *N101C = dyn_cast<ConstantSDNode>(N101);
+ if (N101C) {
+ MVT TruncVT = N1.getValueType();
+ unsigned TruncBitSize = TruncVT.getSizeInBits();
+ APInt ShAmt = N101C->getAPIntValue();
+ if (ShAmt.trunc(TruncBitSize).getZExtValue() == N101C->getValue()) {
+ SDValue N100 = N1.getOperand(0).getOperand(0);
+ return DAG.getNode(ISD::SRL, VT, N0,
+ DAG.getNode(ISD::AND, TruncVT,
+ DAG.getNode(ISD::TRUNCATE, TruncVT, N100),
+ DAG.getConstant(N101C->getValue(), TruncVT)));
+ }
+ }
+ }
// fold operands of srl based on knowledge that the low bits are not
// demanded.
TargetLowering &TLI) {
bool HasCopyToRegUses = false;
bool isTruncFree = TLI.isTruncateFree(N->getValueType(0), N0.getValueType());
- for (SDNode::use_iterator UI = N0.getNode()->use_begin(), UE = N0.getNode()->use_end();
+ for (SDNode::use_iterator UI = N0.getNode()->use_begin(),
+ UE = N0.getNode()->use_end();
UI != UE; ++UI) {
SDNode *User = *UI;
if (User == N)
LN0->isVolatile(),
LN0->getAlignment());
CombineTo(N, ExtLoad);
- CombineTo(N0.getNode(), DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
+ CombineTo(N0.getNode(),
+ DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
ExtLoad.getValue(1));
return SDValue(N, 0); // Return N so it doesn't get rechecked!
}
LN0->isVolatile(),
LN0->getAlignment());
CombineTo(N, ExtLoad);
- CombineTo(N0.getNode(), DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
+ CombineTo(N0.getNode(),
+ DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
ExtLoad.getValue(1));
return SDValue(N, 0); // Return N so it doesn't get rechecked!
}
LN0->getAlignment());
CombineTo(N, ExtLoad);
// Redirect any chain users to the new load.
- DAG.ReplaceAllUsesOfValueWith(SDValue(LN0, 1), SDValue(ExtLoad.getNode(), 1));
+ DAG.ReplaceAllUsesOfValueWith(SDValue(LN0, 1),
+ SDValue(ExtLoad.getNode(), 1));
// If any node needs the original loaded value, recompute it.
if (!LN0->use_empty())
CombineTo(LN0, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
LN0->isVolatile(),
LN0->getAlignment());
CombineTo(N, ExtLoad);
- CombineTo(N0.getNode(), DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
+ CombineTo(N0.getNode(),
+ DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
ExtLoad.getValue(1));
return SDValue(N, 0); // Return N so it doesn't get rechecked!
}
TLI.isConsecutiveLoad(LD2, LD1, LD1VT.getSizeInBits()/8, 1, MFI)) {
LoadSDNode *LD = cast<LoadSDNode>(LD1);
unsigned Align = LD->getAlignment();
- unsigned NewAlign = TLI.getTargetMachine().getTargetData()->
+ unsigned NewAlign = TLI.getTargetData()->
getABITypeAlignment(VT.getTypeForMVT());
if (NewAlign <= Align &&
(!AfterLegalize || TLI.isOperationLegal(ISD::LOAD, VT)))
}
}
- // If the input is a constant, let getNode() fold it.
+ // If the input is a constant, let getNode fold it.
if (isa<ConstantSDNode>(N0) || isa<ConstantFPSDNode>(N0)) {
SDValue Res = DAG.getNode(ISD::BIT_CONVERT, VT, N0);
if (Res.getNode() != N) return Res;
!cast<LoadSDNode>(N0)->isVolatile() &&
(!AfterLegalize || TLI.isOperationLegal(ISD::LOAD, VT))) {
LoadSDNode *LN0 = cast<LoadSDNode>(N0);
- unsigned Align = TLI.getTargetMachine().getTargetData()->
+ unsigned Align = TLI.getTargetData()->
getABITypeAlignment(VT.getTypeForMVT());
unsigned OrigAlign = LN0->getAlignment();
if (Align <= OrigAlign) {
LN0->getSrcValue(), LN0->getSrcValueOffset(),
LN0->isVolatile(), OrigAlign);
AddToWorkList(N);
- CombineTo(N0.getNode(), DAG.getNode(ISD::BIT_CONVERT, N0.getValueType(), Load),
+ CombineTo(N0.getNode(),
+ DAG.getNode(ISD::BIT_CONVERT, N0.getValueType(), Load),
Load.getValue(1));
return Load;
}
// Turn fp_extend(fp_round(X, 1)) -> x since the fp_round doesn't affect the
// value of X.
- if (N0.getOpcode() == ISD::FP_ROUND && N0.getNode()->getConstantOperandVal(1) == 1){
+ if (N0.getOpcode() == ISD::FP_ROUND
+ && N0.getNode()->getConstantOperandVal(1) == 1) {
SDValue In = N0.getOperand(0);
if (In.getValueType() == VT) return In;
if (VT.bitsLT(In.getValueType()))
LN0->isVolatile(),
LN0->getAlignment());
CombineTo(N, ExtLoad);
- CombineTo(N0.getNode(), DAG.getNode(ISD::FP_ROUND, N0.getValueType(), ExtLoad,
- DAG.getIntPtrConstant(1)),
+ CombineTo(N0.getNode(), DAG.getNode(ISD::FP_ROUND, N0.getValueType(),
+ ExtLoad, DAG.getIntPtrConstant(1)),
ExtLoad.getValue(1));
return SDValue(N, 0); // Return N so it doesn't get rechecked!
}
ST->isUnindexed()) {
unsigned Align = ST->getAlignment();
MVT SVT = Value.getOperand(0).getValueType();
- unsigned OrigAlign = TLI.getTargetMachine().getTargetData()->
+ unsigned OrigAlign = TLI.getTargetData()->
getABITypeAlignment(SVT.getTypeForMVT());
if (Align <= OrigAlign &&
((!AfterLegalize && !ST->isVolatile()) ||
// vector with the inserted element.
if (InVec.getOpcode() == ISD::BUILD_VECTOR && isa<ConstantSDNode>(EltNo)) {
unsigned Elt = cast<ConstantSDNode>(EltNo)->getValue();
- SmallVector<SDValue, 8> Ops(InVec.getNode()->op_begin(), InVec.getNode()->op_end());
+ SmallVector<SDValue, 8> Ops(InVec.getNode()->op_begin(),
+ InVec.getNode()->op_end());
if (Elt < Ops.size())
Ops[Elt] = InVal;
return DAG.getNode(ISD::BUILD_VECTOR, InVec.getValueType(),
if (NewLoad) {
// Check the resultant load doesn't need a higher alignment than the
// original load.
- unsigned NewAlign = TLI.getTargetMachine().getTargetData()->
+ unsigned NewAlign = TLI.getTargetData()->
getABITypeAlignment(LVT.getTypeForMVT());
if (NewAlign > Align || !TLI.isOperationLegal(ISD::LOAD, LVT))
return SDValue();
projects / oota-llvm.git / blobdiff