X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FCorrelatedExprs.cpp;h=8d369f2870e4dee0af458ab898493be3ed57052b;hb=e4d87aa2de6e52952dca73716386db09aad5a8fd;hp=d9e96485fc4caec64edd3eeac3d7cde5dbabc189;hpb=5585b335e560207a1e6977ff0f3ef7262f8f979f;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/CorrelatedExprs.cpp b/lib/Transforms/Scalar/CorrelatedExprs.cpp index d9e96485fc4..8d369f2870e 100644 --- a/lib/Transforms/Scalar/CorrelatedExprs.cpp +++ b/lib/Transforms/Scalar/CorrelatedExprs.cpp @@ -1,10 +1,10 @@ //===- CorrelatedExprs.cpp - Pass to detect and eliminated c.e.'s ---------===// -// +// // The LLVM Compiler Infrastructure // // This file was developed by the LLVM research group and is distributed under // the University of Illinois Open Source License. See LICENSE.TXT for details. -// +// //===----------------------------------------------------------------------===// // // Correlated Expression Elimination propagates information from conditional @@ -26,6 +26,7 @@ // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "cee" #include "llvm/Transforms/Scalar.h" #include "llvm/Constants.h" #include "llvm/Pass.h" @@ -38,42 +39,42 @@ #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Support/ConstantRange.h" #include "llvm/Support/CFG.h" -#include "Support/Debug.h" -#include "Support/PostOrderIterator.h" -#include "Support/Statistic.h" +#include "llvm/Support/Debug.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/Statistic.h" #include using namespace llvm; -namespace { - Statistic<> NumSetCCRemoved("cee", "Number of setcc instruction eliminated"); - Statistic<> NumOperandsCann("cee", "Number of operands canonicalized"); - Statistic<> BranchRevectors("cee", "Number of branches revectored"); +STATISTIC(NumCmpRemoved, "Number of cmp instruction eliminated"); +STATISTIC(NumOperandsCann, "Number of operands canonicalized"); +STATISTIC(BranchRevectors, "Number of branches revectored"); +namespace { class ValueInfo; class Relation { - Value *Val; // Relation to what value? - Instruction::BinaryOps Rel; // SetCC relation, or Add if no information + Value *Val; // Relation to what value? + unsigned Rel; // SetCC or ICmp relation, or Add if no information public: Relation(Value *V) : Val(V), Rel(Instruction::Add) {} bool operator<(const Relation &R) const { return Val < R.Val; } Value *getValue() const { return Val; } - Instruction::BinaryOps getRelation() const { return Rel; } + unsigned getRelation() const { return Rel; } // contradicts - Return true if the relationship specified by the operand // contradicts already known information. // - bool contradicts(Instruction::BinaryOps Rel, const ValueInfo &VI) const; + bool contradicts(unsigned Rel, const ValueInfo &VI) const; // incorporate - Incorporate information in the argument into this relation // entry. This assumes that the information doesn't contradict itself. If // any new information is gained, true is returned, otherwise false is // returned to indicate that nothing was updated. // - bool incorporate(Instruction::BinaryOps Rel, ValueInfo &VI); + bool incorporate(unsigned Rel, ValueInfo &VI); // KnownResult - Whether or not this condition determines the result of a - // setcc in the program. False & True are intentionally 0 & 1 so we can - // convert to bool by casting after checking for unknown. + // setcc or icmp in the program. False & True are intentionally 0 & 1 + // so we can convert to bool by casting after checking for unknown. // enum KnownResult { KnownFalse = 0, KnownTrue = 1, Unknown = 2 }; @@ -81,7 +82,7 @@ namespace { // the specified relationship is true or false, return that. If we cannot // determine the result required, return Unknown. // - KnownResult getImpliedResult(Instruction::BinaryOps Rel) const; + KnownResult getImpliedResult(unsigned Rel) const; // print - Output this relation to the specified stream void print(std::ostream &OS) const; @@ -134,7 +135,8 @@ namespace { Relation &getRelation(Value *V) { // Binary search for V's entry... std::vector::iterator I = - std::lower_bound(Relationships.begin(), Relationships.end(), V); + std::lower_bound(Relationships.begin(), Relationships.end(), + Relation(V)); // If we found the entry, return it... if (I != Relationships.end() && I->getValue() == V) @@ -147,7 +149,8 @@ namespace { const Relation *requestRelation(Value *V) const { // Binary search for V's entry... std::vector::const_iterator I = - std::lower_bound(Relationships.begin(), Relationships.end(), V); + std::lower_bound(Relationships.begin(), Relationships.end(), + Relation(V)); if (I != Relationships.end() && I->getValue() == V) return &*I; return 0; @@ -178,7 +181,7 @@ namespace { // empty - return true if this region has no information known about it. bool empty() const { return ValueMap.empty(); } - + const RegionInfo &operator=(const RegionInfo &RI) { ValueMap = RI.ValueMap; return *this; @@ -204,7 +207,7 @@ namespace { if (I != ValueMap.end()) return &I->second; return 0; } - + /// removeValueInfo - Remove anything known about V from our records. This /// works whether or not we know anything about V. /// @@ -217,14 +220,14 @@ namespace { class CEE : public FunctionPass { std::map RankMap; std::map RegionInfoMap; - DominatorSet *DS; + ETForest *EF; DominatorTree *DT; public: virtual bool runOnFunction(Function &F); // We don't modify the program, so we preserve all analyses virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addRequiredID(BreakCriticalEdgesID); }; @@ -243,7 +246,7 @@ namespace { void BuildRankMap(Function &F); unsigned getRank(Value *V) const { - if (isa(V) || isa(V)) return 0; + if (isa(V)) return 0; std::map::const_iterator I = RankMap.find(V); if (I != RankMap.end()) return I->second; return 0; // Must be some other global thing @@ -264,28 +267,28 @@ namespace { const std::vector &RegionExitBlocks); void PropagateBranchInfo(BranchInst *BI); + void PropagateSwitchInfo(SwitchInst *SI); void PropagateEquality(Value *Op0, Value *Op1, RegionInfo &RI); - void PropagateRelation(Instruction::BinaryOps Opcode, Value *Op0, + void PropagateRelation(unsigned Opcode, Value *Op0, Value *Op1, RegionInfo &RI); void UpdateUsersOfValue(Value *V, RegionInfo &RI); void IncorporateInstruction(Instruction *Inst, RegionInfo &RI); void ComputeReplacements(RegionInfo &RI); - - // getSetCCResult - Given a setcc instruction, determine if the result is + // getCmpResult - Given a icmp instruction, determine if the result is // determined by facts we already know about the region under analysis. - // Return KnownTrue, KnownFalse, or Unknown based on what we can determine. - // - Relation::KnownResult getSetCCResult(SetCondInst *SC, const RegionInfo &RI); - + // Return KnownTrue, KnownFalse, or UnKnown based on what we can determine. + Relation::KnownResult getCmpResult(CmpInst *ICI, const RegionInfo &RI); bool SimplifyBasicBlock(BasicBlock &BB, const RegionInfo &RI); bool SimplifyInstruction(Instruction *Inst, const RegionInfo &RI); - }; - RegisterOpt X("cee", "Correlated Expression Elimination"); + }; + RegisterPass X("cee", "Correlated Expression Elimination"); } -Pass *llvm::createCorrelatedExpressionEliminationPass() { return new CEE(); } +FunctionPass *llvm::createCorrelatedExpressionEliminationPass() { + return new CEE(); +} bool CEE::runOnFunction(Function &F) { @@ -295,9 +298,9 @@ bool CEE::runOnFunction(Function &F) { // Traverse the dominator tree, computing information for each node in the // tree. Note that our traversal will not even touch unreachable basic // blocks. - DS = &getAnalysis(); + EF = &getAnalysis(); DT = &getAnalysis(); - + std::set VisitedBlocks; bool Changed = TransformRegion(&F.getEntryBlock(), VisitedBlocks); @@ -330,7 +333,7 @@ bool CEE::TransformRegion(BasicBlock *BB, std::set &VisitedBlocks){ ComputeReplacements(RI); // If debugging, print computed region information... - DEBUG(RI.print(std::cerr)); + DEBUG(RI.print(*cerr.stream())); // Simplify the contents of this block... bool Changed = SimplifyBasicBlock(*BB, RI); @@ -355,9 +358,12 @@ bool CEE::TransformRegion(BasicBlock *BB, std::set &VisitedBlocks){ // Now that all of our successors have information if they deserve it, // propagate any information our terminator instruction finds to our // successors. - if (BranchInst *BI = dyn_cast(TI)) + if (BranchInst *BI = dyn_cast(TI)) { if (BI->isConditional()) PropagateBranchInfo(BI); + } else if (SwitchInst *SI = dyn_cast(TI)) { + PropagateSwitchInfo(SI); + } // If this is a branch to a block outside our region that simply performs // another conditional branch, one whose outcome is known inside of this @@ -424,7 +430,7 @@ bool CEE::ForwardCorrelatedEdgeDestination(TerminatorInst *TI, unsigned SuccNo, // Check to see if we dominate the block. If so, this block will get the // condition turned to a constant anyway. // - //if (DS->dominates(RI.getEntryBlock(), BB)) + //if (EF->dominates(RI.getEntryBlock(), BB)) // return 0; BasicBlock *BB = TI->getParent(); @@ -439,12 +445,12 @@ bool CEE::ForwardCorrelatedEdgeDestination(TerminatorInst *TI, unsigned SuccNo, return false; // We can only forward the branch over the block if the block ends with a - // setcc we can determine the outcome for. + // cmp we can determine the outcome for. // // FIXME: we can make this more generic. Code below already handles more // generic case. - SetCondInst *SCI = dyn_cast(BI->getCondition()); - if (SCI == 0) return false; + if (!isa(BI->getCondition())) + return false; // Make a new RegionInfo structure so that we can simulate the effect of the // PHI nodes in the block we are skipping over... @@ -456,34 +462,35 @@ bool CEE::ForwardCorrelatedEdgeDestination(TerminatorInst *TI, unsigned SuccNo, for (BasicBlock::iterator I = OldSucc->begin(), E = OldSucc->end(); I!=E; ++I) if (I->getType() != Type::VoidTy) NewRI.removeValueInfo(I); - + // Put the newly discovered information into the RegionInfo... for (BasicBlock::iterator I = OldSucc->begin(), E = OldSucc->end(); I!=E; ++I) if (PHINode *PN = dyn_cast(I)) { int OpNum = PN->getBasicBlockIndex(BB); assert(OpNum != -1 && "PHI doesn't have incoming edge for predecessor!?"); - PropagateEquality(PN, PN->getIncomingValue(OpNum), NewRI); - } else if (SetCondInst *SCI = dyn_cast(I)) { - Relation::KnownResult Res = getSetCCResult(SCI, NewRI); + PropagateEquality(PN, PN->getIncomingValue(OpNum), NewRI); + } else if (CmpInst *CI = dyn_cast(I)) { + Relation::KnownResult Res = getCmpResult(CI, NewRI); if (Res == Relation::Unknown) return false; - PropagateEquality(SCI, ConstantBool::get(Res), NewRI); + PropagateEquality(CI, ConstantBool::get(Res), NewRI); } else { assert(isa(*I) && "Unexpected instruction type!"); } - + // Compute the facts implied by what we have discovered... ComputeReplacements(NewRI); ValueInfo &PredicateVI = NewRI.getValueInfo(BI->getCondition()); if (PredicateVI.getReplacement() && - isa(PredicateVI.getReplacement())) { + isa(PredicateVI.getReplacement()) && + !isa(PredicateVI.getReplacement())) { ConstantBool *CB = cast(PredicateVI.getReplacement()); // Forward to the successor that corresponds to the branch we will take. ForwardSuccessorTo(TI, SuccNo, BI->getSuccessor(!CB->getValue()), NewRI); return true; } - + return false; } @@ -507,11 +514,10 @@ void CEE::ForwardSuccessorTo(TerminatorInst *TI, unsigned SuccNo, BasicBlock *OldSucc = TI->getSuccessor(SuccNo); BasicBlock *BB = TI->getParent(); - DEBUG(std::cerr << "Forwarding branch in basic block %" << BB->getName() - << " from block %" << OldSucc->getName() << " to block %" - << Dest->getName() << "\n"); - - DEBUG(std::cerr << "Before forwarding: " << *BB->getParent()); + DOUT << "Forwarding branch in basic block %" << BB->getName() + << " from block %" << OldSucc->getName() << " to block %" + << Dest->getName() << "\n" + << "Before forwarding: " << *BB->getParent(); // Because we know that there cannot be critical edges in the flow graph, and // that OldSucc has multiple outgoing edges, this means that Dest cannot have @@ -537,7 +543,7 @@ void CEE::ForwardSuccessorTo(TerminatorInst *TI, unsigned SuccNo, // insert dead phi nodes, but it is more trouble to see if they are used than // to just blindly insert them. // - if (DS->dominates(OldSucc, Dest)) { + if (EF->dominates(OldSucc, Dest)) { // RegionExitBlocks - Find all of the blocks that are not dominated by Dest, // but have predecessors that are. Additionally, prune down the set to only // include blocks that are dominated by OldSucc as well. @@ -571,15 +577,15 @@ void CEE::ForwardSuccessorTo(TerminatorInst *TI, unsigned SuccNo, // edge from the PHI node, and we need to replace any references to the PHI // node with a new value. // - for (BasicBlock::iterator I = OldSucc->begin(); - PHINode *PN = dyn_cast(I); ) { + for (BasicBlock::iterator I = OldSucc->begin(); isa(I); ) { + PHINode *PN = cast(I); // Get the value flowing across the old edge and remove the PHI node entry // for this edge: we are about to remove the edge! Don't remove the PHI // node yet though if this is the last edge into it. Value *EdgeValue = PN->removeIncomingValue(BB, false); - // Make sure that anything that used to use PN now refers to EdgeValue + // Make sure that anything that used to use PN now refers to EdgeValue ReplaceUsesOfValueInRegion(PN, EdgeValue, Dest); // If there is only one value left coming into the PHI node, replace the PHI @@ -600,7 +606,7 @@ void CEE::ForwardSuccessorTo(TerminatorInst *TI, unsigned SuccNo, ++I; // Otherwise, move on to the next PHI node } } - + // Actually revector the branch now... TI->setSuccessor(SuccNo, Dest); @@ -611,15 +617,14 @@ void CEE::ForwardSuccessorTo(TerminatorInst *TI, unsigned SuccNo, // Make sure that we don't introduce critical edges from oldsucc now! for (unsigned i = 0, e = OldSucc->getTerminator()->getNumSuccessors(); i != e; ++i) - if (isCriticalEdge(OldSucc->getTerminator(), i)) - SplitCriticalEdge(OldSucc->getTerminator(), i, this); + SplitCriticalEdge(OldSucc->getTerminator(), i, this); // Since we invalidated the CFG, recalculate the dominator set so that it is // useful for later processing! // FIXME: This is much worse than it really should be! - //DS->recalculate(); + //EF->recalculate(); - DEBUG(std::cerr << "After forwarding: " << *BB->getParent()); + DOUT << "After forwarding: " << *BB->getParent(); } /// ReplaceUsesOfValueInRegion - This method replaces all uses of Orig with uses @@ -631,14 +636,14 @@ void CEE::ReplaceUsesOfValueInRegion(Value *Orig, Value *New, assert(Orig != New && "Cannot replace value with itself"); std::vector InstsToChange; std::vector PHIsToChange; - InstsToChange.reserve(Orig->use_size()); + InstsToChange.reserve(Orig->getNumUses()); // Loop over instructions adding them to InstsToChange vector, this allows us // an easy way to avoid invalidating the use_iterator at a bad time. for (Value::use_iterator I = Orig->use_begin(), E = Orig->use_end(); I != E; ++I) if (Instruction *User = dyn_cast(*I)) - if (DS->dominates(RegionDominator, User->getParent())) + if (EF->dominates(RegionDominator, User->getParent())) InstsToChange.push_back(User); else if (PHINode *PN = dyn_cast(User)) { PHIsToChange.push_back(PN); @@ -651,7 +656,7 @@ void CEE::ReplaceUsesOfValueInRegion(Value *Orig, Value *New, PHINode *PN = PHIsToChange[i]; for (unsigned j = 0, e = PN->getNumIncomingValues(); j != e; ++j) if (PN->getIncomingValue(j) == Orig && - DS->dominates(RegionDominator, PN->getIncomingBlock(j))) + EF->dominates(RegionDominator, PN->getIncomingBlock(j))) PN->setIncomingValue(j, New); } @@ -665,7 +670,7 @@ void CEE::ReplaceUsesOfValueInRegion(Value *Orig, Value *New, // values that correspond to basic blocks in the region. for (unsigned j = 0, e = PN->getNumIncomingValues(); j != e; ++j) if (PN->getIncomingValue(j) == Orig && - DS->dominates(RegionDominator, PN->getIncomingBlock(j))) + EF->dominates(RegionDominator, PN->getIncomingBlock(j))) PN->setIncomingValue(j, New); } else { @@ -675,18 +680,18 @@ void CEE::ReplaceUsesOfValueInRegion(Value *Orig, Value *New, static void CalcRegionExitBlocks(BasicBlock *Header, BasicBlock *BB, std::set &Visited, - DominatorSet &DS, + ETForest &EF, std::vector &RegionExitBlocks) { if (Visited.count(BB)) return; Visited.insert(BB); - if (DS.dominates(Header, BB)) { // Block in the region, recursively traverse + if (EF.dominates(Header, BB)) { // Block in the region, recursively traverse for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) - CalcRegionExitBlocks(Header, *I, Visited, DS, RegionExitBlocks); + CalcRegionExitBlocks(Header, *I, Visited, EF, RegionExitBlocks); } else { // Header does not dominate this block, but we have a predecessor that does // dominate us. Add ourself to the list. - RegionExitBlocks.push_back(BB); + RegionExitBlocks.push_back(BB); } } @@ -699,11 +704,11 @@ void CEE::CalculateRegionExitBlocks(BasicBlock *BB, BasicBlock *OldSucc, std::set Visited; // Don't infinite loop // Recursively calculate blocks we are interested in... - CalcRegionExitBlocks(BB, BB, Visited, *DS, RegionExitBlocks); - + CalcRegionExitBlocks(BB, BB, Visited, *EF, RegionExitBlocks); + // Filter out blocks that are not dominated by OldSucc... for (unsigned i = 0; i != RegionExitBlocks.size(); ) { - if (DS->dominates(OldSucc, RegionExitBlocks[i])) + if (EF->dominates(OldSucc, RegionExitBlocks[i])) ++i; // Block is ok, keep it. else { // Move to end of list... @@ -717,7 +722,6 @@ void CEE::InsertRegionExitMerges(PHINode *BBVal, Instruction *OldVal, const std::vector &RegionExitBlocks) { assert(BBVal->getType() == OldVal->getType() && "Should be derived values!"); BasicBlock *BB = BBVal->getParent(); - BasicBlock *OldSucc = OldVal->getParent(); // Loop over all of the blocks we have to place PHIs in, doing it. for (unsigned i = 0, e = RegionExitBlocks.size(); i != e; ++i) { @@ -733,9 +737,9 @@ void CEE::InsertRegionExitMerges(PHINode *BBVal, Instruction *OldVal, PI != PE; ++PI) { // If the incoming edge is from the region dominated by BB, use BBVal, // otherwise use OldVal. - NewPN->addIncoming(DS->dominates(BB, *PI) ? BBVal : OldVal, *PI); + NewPN->addIncoming(EF->dominates(BB, *PI) ? BBVal : OldVal, *PI); } - + // Now make everyone dominated by this block use this new value! ReplaceUsesOfValueInRegion(OldVal, NewPN, FBlock); } @@ -754,7 +758,7 @@ void CEE::BuildRankMap(Function &F) { unsigned Rank = 1; // Skip rank zero. // Number the arguments... - for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I) + for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) RankMap[I] = Rank++; // Number the instructions in reverse post order... @@ -778,16 +782,32 @@ void CEE::PropagateBranchInfo(BranchInst *BI) { // Propagate information into the true block... // - PropagateEquality(BI->getCondition(), ConstantBool::True, + PropagateEquality(BI->getCondition(), ConstantBool::getTrue(), getRegionInfo(BI->getSuccessor(0))); - + // Propagate information into the false block... // - PropagateEquality(BI->getCondition(), ConstantBool::False, + PropagateEquality(BI->getCondition(), ConstantBool::getFalse(), getRegionInfo(BI->getSuccessor(1))); } +// PropagateSwitchInfo - We need to propagate the value tested by the +// switch statement through each case block. +// +void CEE::PropagateSwitchInfo(SwitchInst *SI) { + // Propagate information down each of our non-default case labels. We + // don't yet propagate information down the default label, because a + // potentially large number of inequality constraints provide less + // benefit per unit work than a single equality constraint. + // + Value *cond = SI->getCondition(); + for (unsigned i = 1; i < SI->getNumSuccessors(); ++i) + PropagateEquality(cond, SI->getSuccessorValue(i), + getRegionInfo(SI->getSuccessor(i))); +} + + // PropagateEquality - If we discover that two values are equal to each other in // a specified region, propagate this knowledge recursively. // @@ -804,7 +824,8 @@ void CEE::PropagateEquality(Value *Op0, Value *Op1, RegionInfo &RI) { Relation &KnownRelation = VI.getRelation(Op1); // If we already know they're equal, don't reprocess... - if (KnownRelation.getRelation() == Instruction::SetEQ) + if (KnownRelation.getRelation() == FCmpInst::FCMP_OEQ || + KnownRelation.getRelation() == ICmpInst::ICMP_EQ) return; // If this is boolean, check to see if one of the operands is a constant. If @@ -822,7 +843,7 @@ void CEE::PropagateEquality(Value *Op0, Value *Op1, RegionInfo &RI) { PropagateEquality(Inst->getOperand(0), CB, RI); PropagateEquality(Inst->getOperand(1), CB, RI); } - + // If we know that this instruction is an OR instruction, and the result // is false, this means that both operands to the OR are know to be false // as well. @@ -831,7 +852,7 @@ void CEE::PropagateEquality(Value *Op0, Value *Op1, RegionInfo &RI) { PropagateEquality(Inst->getOperand(0), CB, RI); PropagateEquality(Inst->getOperand(1), CB, RI); } - + // If we know that this instruction is a NOT instruction, we know that the // operand is known to be the inverse of whatever the current value is. // @@ -840,32 +861,55 @@ void CEE::PropagateEquality(Value *Op0, Value *Op1, RegionInfo &RI) { PropagateEquality(BinaryOperator::getNotArgument(BOp), ConstantBool::get(!CB->getValue()), RI); - // If we know the value of a SetCC instruction, propagate the information + // If we know the value of a FCmp instruction, propagate the information // about the relation into this region as well. // - if (SetCondInst *SCI = dyn_cast(Inst)) { + if (FCmpInst *FCI = dyn_cast(Inst)) { if (CB->getValue()) { // If we know the condition is true... // Propagate info about the LHS to the RHS & RHS to LHS - PropagateRelation(SCI->getOpcode(), SCI->getOperand(0), - SCI->getOperand(1), RI); - PropagateRelation(SCI->getSwappedCondition(), - SCI->getOperand(1), SCI->getOperand(0), RI); + PropagateRelation(FCI->getPredicate(), FCI->getOperand(0), + FCI->getOperand(1), RI); + PropagateRelation(FCI->getSwappedPredicate(), + FCI->getOperand(1), FCI->getOperand(0), RI); } else { // If we know the condition is false... // We know the opposite of the condition is true... - Instruction::BinaryOps C = SCI->getInverseCondition(); - - PropagateRelation(C, SCI->getOperand(0), SCI->getOperand(1), RI); - PropagateRelation(SetCondInst::getSwappedCondition(C), - SCI->getOperand(1), SCI->getOperand(0), RI); + FCmpInst::Predicate C = FCI->getInversePredicate(); + + PropagateRelation(C, FCI->getOperand(0), FCI->getOperand(1), RI); + PropagateRelation(FCmpInst::getSwappedPredicate(C), + FCI->getOperand(1), FCI->getOperand(0), RI); + } + } + + // If we know the value of a ICmp instruction, propagate the information + // about the relation into this region as well. + // + if (ICmpInst *ICI = dyn_cast(Inst)) { + if (CB->getValue()) { // If we know the condition is true... + // Propagate info about the LHS to the RHS & RHS to LHS + PropagateRelation(ICI->getPredicate(), ICI->getOperand(0), + ICI->getOperand(1), RI); + PropagateRelation(ICI->getSwappedPredicate(), ICI->getOperand(1), + ICI->getOperand(1), RI); + + } else { // If we know the condition is false ... + // We know the opposite of the condition is true... + ICmpInst::Predicate C = ICI->getInversePredicate(); + + PropagateRelation(C, ICI->getOperand(0), ICI->getOperand(1), RI); + PropagateRelation(ICmpInst::getSwappedPredicate(C), + ICI->getOperand(1), ICI->getOperand(0), RI); } } } } // Propagate information about Op0 to Op1 & visa versa - PropagateRelation(Instruction::SetEQ, Op0, Op1, RI); - PropagateRelation(Instruction::SetEQ, Op1, Op0, RI); + PropagateRelation(ICmpInst::ICMP_EQ, Op0, Op1, RI); + PropagateRelation(ICmpInst::ICMP_EQ, Op1, Op0, RI); + PropagateRelation(FCmpInst::FCMP_OEQ, Op0, Op1, RI); + PropagateRelation(FCmpInst::FCMP_OEQ, Op1, Op0, RI); } @@ -873,7 +917,7 @@ void CEE::PropagateEquality(Value *Op0, Value *Op1, RegionInfo &RI) { // blocks in the specified region. Propagate the information about Op0 and // anything derived from it into this region. // -void CEE::PropagateRelation(Instruction::BinaryOps Opcode, Value *Op0, +void CEE::PropagateRelation(unsigned Opcode, Value *Op0, Value *Op1, RegionInfo &RI) { assert(Op0->getType() == Op1->getType() && "Equal types expected!"); @@ -897,9 +941,12 @@ void CEE::PropagateRelation(Instruction::BinaryOps Opcode, Value *Op0, // if (Op1R.contradicts(Opcode, VI)) { Op1R.contradicts(Opcode, VI); - std::cerr << "Contradiction found for opcode: " - << Instruction::getOpcodeName(Opcode) << "\n"; - Op1R.print(std::cerr); + cerr << "Contradiction found for opcode: " + << ((isa(Op0)||isa(Op1)) ? + Instruction::getOpcodeName(Instruction::ICmp) : + Instruction::getOpcodeName(Opcode)) + << "\n"; + Op1R.print(*cerr.stream()); return; } @@ -931,7 +978,7 @@ void CEE::UpdateUsersOfValue(Value *V, RegionInfo &RI) { // here. This check is also effectively checking to make sure that Inst // is in the same function as our region (in case V is a global f.e.). // - if (DS->properlyDominates(Inst->getParent(), RI.getEntryBlock())) + if (EF->properlyDominates(Inst->getParent(), RI.getEntryBlock())) IncorporateInstruction(Inst, RI); } } @@ -941,12 +988,11 @@ void CEE::UpdateUsersOfValue(Value *V, RegionInfo &RI) { // value produced by this instruction // void CEE::IncorporateInstruction(Instruction *Inst, RegionInfo &RI) { - if (SetCondInst *SCI = dyn_cast(Inst)) { + if (CmpInst *CI = dyn_cast(Inst)) { // See if we can figure out a result for this instruction... - Relation::KnownResult Result = getSetCCResult(SCI, RI); + Relation::KnownResult Result = getCmpResult(CI, RI); if (Result != Relation::Unknown) { - PropagateEquality(SCI, Result ? ConstantBool::True : ConstantBool::False, - RI); + PropagateEquality(CI, ConstantBool::get(Result != 0), RI); } } } @@ -980,7 +1026,14 @@ void CEE::ComputeReplacements(RegionInfo &RI) { // Loop over the relationships known about Op0. const std::vector &Relationships = VI.getRelationships(); for (unsigned i = 0, e = Relationships.size(); i != e; ++i) - if (Relationships[i].getRelation() == Instruction::SetEQ) { + if (Relationships[i].getRelation() == FCmpInst::FCMP_OEQ) { + unsigned R = getRank(Relationships[i].getValue()); + if (R < MinRank) { + MinRank = R; + Replacement = Relationships[i].getValue(); + } + } + else if (Relationships[i].getRelation() == ICmpInst::ICMP_EQ) { unsigned R = getRank(Relationships[i].getValue()); if (R < MinRank) { MinRank = R; @@ -1006,17 +1059,17 @@ bool CEE::SimplifyBasicBlock(BasicBlock &BB, const RegionInfo &RI) { // Convert instruction arguments to canonical forms... Changed |= SimplifyInstruction(Inst, RI); - if (SetCondInst *SCI = dyn_cast(Inst)) { + if (CmpInst *CI = dyn_cast(Inst)) { // Try to simplify a setcc instruction based on inherited information - Relation::KnownResult Result = getSetCCResult(SCI, RI); + Relation::KnownResult Result = getCmpResult(CI, RI); if (Result != Relation::Unknown) { - DEBUG(std::cerr << "Replacing setcc with " << Result - << " constant: " << SCI); + DEBUG(cerr << "Replacing icmp with " << Result + << " constant: " << *CI); - SCI->replaceAllUsesWith(ConstantBool::get((bool)Result)); + CI->replaceAllUsesWith(ConstantBool::get((bool)Result)); // The instruction is now dead, remove it from the program. - SCI->getParent()->getInstList().erase(SCI); - ++NumSetCCRemoved; + CI->getParent()->getInstList().erase(CI); + ++NumCmpRemoved; Changed = true; } } @@ -1038,8 +1091,8 @@ bool CEE::SimplifyInstruction(Instruction *I, const RegionInfo &RI) { if (Value *Repl = VI->getReplacement()) { // If we know if a replacement with lower rank than Op0, make the // replacement now. - DEBUG(std::cerr << "In Inst: " << I << " Replacing operand #" << i - << " with " << Repl << "\n"); + DOUT << "In Inst: " << *I << " Replacing operand #" << i + << " with " << *Repl << "\n"; I->setOperand(i, Repl); Changed = true; ++NumOperandsCann; @@ -1048,33 +1101,35 @@ bool CEE::SimplifyInstruction(Instruction *I, const RegionInfo &RI) { return Changed; } - -// getSetCCResult - Try to simplify a setcc instruction based on information -// inherited from a dominating setcc instruction. V is one of the operands to -// the setcc instruction, and VI is the set of information known about it. We +// getCmpResult - Try to simplify a cmp instruction based on information +// inherited from a dominating icmp instruction. V is one of the operands to +// the icmp instruction, and VI is the set of information known about it. We // take two cases into consideration here. If the comparison is against a // constant value, we can use the constant range to see if the comparison is // possible to succeed. If it is not a comparison against a constant, we check // to see if there is a known relationship between the two values. If so, we // may be able to eliminate the check. // -Relation::KnownResult CEE::getSetCCResult(SetCondInst *SCI, - const RegionInfo &RI) { - Value *Op0 = SCI->getOperand(0), *Op1 = SCI->getOperand(1); - Instruction::BinaryOps Opcode = SCI->getOpcode(); - +Relation::KnownResult CEE::getCmpResult(CmpInst *CI, + const RegionInfo &RI) { + Value *Op0 = CI->getOperand(0), *Op1 = CI->getOperand(1); + unsigned short predicate = CI->getPredicate(); + if (isa(Op0)) { if (isa(Op1)) { - if (Constant *Result = ConstantFoldInstruction(SCI)) { - // Wow, this is easy, directly eliminate the SetCondInst. - DEBUG(std::cerr << "Replacing setcc with constant fold: " << SCI); + if (Constant *Result = ConstantFoldInstruction(CI)) { + // Wow, this is easy, directly eliminate the ICmpInst. + DEBUG(cerr << "Replacing cmp with constant fold: " << *CI); return cast(Result)->getValue() ? Relation::KnownTrue : Relation::KnownFalse; } } else { // We want to swap this instruction so that operand #0 is the constant. std::swap(Op0, Op1); - Opcode = SCI->getSwappedCondition(); + if (isa(CI)) + predicate = cast(CI)->getSwappedPredicate(); + else + predicate = cast(CI)->getSwappedPredicate(); } } @@ -1086,16 +1141,17 @@ Relation::KnownResult CEE::getSetCCResult(SetCondInst *SCI, // At this point, we know that if we have a constant argument that it is in // Op1. Check to see if we know anything about comparing value with a - // constant, and if we can use this info to fold the setcc. + // constant, and if we can use this info to fold the icmp. // if (ConstantIntegral *C = dyn_cast(Op1)) { // Check to see if we already know the result of this comparison... - ConstantRange R = ConstantRange(Opcode, C); - ConstantRange Int = R.intersectWith(Op0VI->getBounds()); + ConstantRange R = ConstantRange(predicate, C); + ConstantRange Int = R.intersectWith(Op0VI->getBounds(), + ICmpInst::isSignedPredicate(ICmpInst::Predicate(predicate))); // If the intersection of the two ranges is empty, then the condition // could never be true! - // + // if (Int.isEmptySet()) { Result = Relation::KnownFalse; @@ -1113,7 +1169,7 @@ Relation::KnownResult CEE::getSetCCResult(SetCondInst *SCI, // // Do we have value information about Op0 and a relation to Op1? if (const Relation *Op2R = Op0VI->requestRelation(Op1)) - Result = Op2R->getImpliedResult(Opcode); + Result = Op2R->getImpliedResult(predicate); } } return Result; @@ -1123,23 +1179,10 @@ Relation::KnownResult CEE::getSetCCResult(SetCondInst *SCI, // Relation Implementation //===----------------------------------------------------------------------===// -// CheckCondition - Return true if the specified condition is false. Bound may -// be null. -static bool CheckCondition(Constant *Bound, Constant *C, - Instruction::BinaryOps BO) { - assert(C != 0 && "C is not specified!"); - if (Bound == 0) return false; - - Constant *Val = ConstantExpr::get(BO, Bound, C); - if (ConstantBool *CB = dyn_cast(Val)) - return !CB->getValue(); // Return true if the condition is false... - return false; -} - // contradicts - Return true if the relationship specified by the operand // contradicts already known information. // -bool Relation::contradicts(Instruction::BinaryOps Op, +bool Relation::contradicts(unsigned Op, const ValueInfo &VI) const { assert (Op != Instruction::Add && "Invalid relation argument!"); @@ -1147,24 +1190,48 @@ bool Relation::contradicts(Instruction::BinaryOps Op, // does not contradict properties known about the bounds of the constant. // if (ConstantIntegral *C = dyn_cast(Val)) - if (ConstantRange(Op, C).intersectWith(VI.getBounds()).isEmptySet()) - return true; + if (Op >= ICmpInst::FIRST_ICMP_PREDICATE && + Op <= ICmpInst::LAST_ICMP_PREDICATE) + if (ConstantRange(Op, C).intersectWith(VI.getBounds(), + ICmpInst::isSignedPredicate(ICmpInst::Predicate(Op))).isEmptySet()) + return true; switch (Rel) { default: assert(0 && "Unknown Relationship code!"); case Instruction::Add: return false; // Nothing known, nothing contradicts - case Instruction::SetEQ: - return Op == Instruction::SetLT || Op == Instruction::SetGT || - Op == Instruction::SetNE; - case Instruction::SetNE: return Op == Instruction::SetEQ; - case Instruction::SetLE: return Op == Instruction::SetGT; - case Instruction::SetGE: return Op == Instruction::SetLT; - case Instruction::SetLT: - return Op == Instruction::SetEQ || Op == Instruction::SetGT || - Op == Instruction::SetGE; - case Instruction::SetGT: - return Op == Instruction::SetEQ || Op == Instruction::SetLT || - Op == Instruction::SetLE; + case ICmpInst::ICMP_EQ: + return Op == ICmpInst::ICMP_ULT || Op == ICmpInst::ICMP_SLT || + Op == ICmpInst::ICMP_UGT || Op == ICmpInst::ICMP_SGT || + Op == ICmpInst::ICMP_NE; + case ICmpInst::ICMP_NE: return Op == ICmpInst::ICMP_EQ; + case ICmpInst::ICMP_ULE: + case ICmpInst::ICMP_SLE: return Op == ICmpInst::ICMP_UGT || + Op == ICmpInst::ICMP_SGT; + case ICmpInst::ICMP_UGE: + case ICmpInst::ICMP_SGE: return Op == ICmpInst::ICMP_ULT || + Op == ICmpInst::ICMP_SLT; + case ICmpInst::ICMP_ULT: + case ICmpInst::ICMP_SLT: + return Op == ICmpInst::ICMP_EQ || Op == ICmpInst::ICMP_UGT || + Op == ICmpInst::ICMP_SGT || Op == ICmpInst::ICMP_UGE || + Op == ICmpInst::ICMP_SGE; + case ICmpInst::ICMP_UGT: + case ICmpInst::ICMP_SGT: + return Op == ICmpInst::ICMP_EQ || Op == ICmpInst::ICMP_ULT || + Op == ICmpInst::ICMP_SLT || Op == ICmpInst::ICMP_ULE || + Op == ICmpInst::ICMP_SLE; + case FCmpInst::FCMP_OEQ: + return Op == FCmpInst::FCMP_OLT || Op == FCmpInst::FCMP_OGT || + Op == FCmpInst::FCMP_ONE; + case FCmpInst::FCMP_ONE: return Op == FCmpInst::FCMP_OEQ; + case FCmpInst::FCMP_OLE: return Op == FCmpInst::FCMP_OGT; + case FCmpInst::FCMP_OGE: return Op == FCmpInst::FCMP_OLT; + case FCmpInst::FCMP_OLT: + return Op == FCmpInst::FCMP_OEQ || Op == FCmpInst::FCMP_OGT || + Op == FCmpInst::FCMP_OGE; + case FCmpInst::FCMP_OGT: + return Op == FCmpInst::FCMP_OEQ || Op == FCmpInst::FCMP_OLT || + Op == FCmpInst::FCMP_OLE; } } @@ -1173,7 +1240,7 @@ bool Relation::contradicts(Instruction::BinaryOps Op, // new information is gained, true is returned, otherwise false is returned to // indicate that nothing was updated. // -bool Relation::incorporate(Instruction::BinaryOps Op, ValueInfo &VI) { +bool Relation::incorporate(unsigned Op, ValueInfo &VI) { assert(!contradicts(Op, VI) && "Cannot incorporate contradictory information!"); @@ -1181,30 +1248,64 @@ bool Relation::incorporate(Instruction::BinaryOps Op, ValueInfo &VI) { // range that is possible for the value to have... // if (ConstantIntegral *C = dyn_cast(Val)) - VI.getBounds() = ConstantRange(Op, C).intersectWith(VI.getBounds()); + if (Op >= ICmpInst::FIRST_ICMP_PREDICATE && + Op <= ICmpInst::LAST_ICMP_PREDICATE) + VI.getBounds() = ConstantRange(Op, C).intersectWith(VI.getBounds(), + ICmpInst::isSignedPredicate(ICmpInst::Predicate(Op))); switch (Rel) { default: assert(0 && "Unknown prior value!"); case Instruction::Add: Rel = Op; return true; - case Instruction::SetEQ: return false; // Nothing is more precise - case Instruction::SetNE: return false; // Nothing is more precise - case Instruction::SetLT: return false; // Nothing is more precise - case Instruction::SetGT: return false; // Nothing is more precise - case Instruction::SetLE: - if (Op == Instruction::SetEQ || Op == Instruction::SetLT) { + case ICmpInst::ICMP_EQ: + case ICmpInst::ICMP_NE: + case ICmpInst::ICMP_ULT: + case ICmpInst::ICMP_SLT: + case ICmpInst::ICMP_UGT: + case ICmpInst::ICMP_SGT: return false; // Nothing is more precise + case ICmpInst::ICMP_ULE: + case ICmpInst::ICMP_SLE: + if (Op == ICmpInst::ICMP_EQ || Op == ICmpInst::ICMP_ULT || + Op == ICmpInst::ICMP_SLT) { Rel = Op; return true; - } else if (Op == Instruction::SetNE) { - Rel = Instruction::SetLT; + } else if (Op == ICmpInst::ICMP_NE) { + Rel = Rel == ICmpInst::ICMP_ULE ? ICmpInst::ICMP_ULT : + ICmpInst::ICMP_SLT; return true; } return false; - case Instruction::SetGE: return Op == Instruction::SetLT; - if (Op == Instruction::SetEQ || Op == Instruction::SetGT) { + case ICmpInst::ICMP_UGE: + case ICmpInst::ICMP_SGE: + if (Op == ICmpInst::ICMP_EQ || ICmpInst::ICMP_UGT || + Op == ICmpInst::ICMP_SGT) { Rel = Op; return true; - } else if (Op == Instruction::SetNE) { - Rel = Instruction::SetGT; + } else if (Op == ICmpInst::ICMP_NE) { + Rel = Rel == ICmpInst::ICMP_UGE ? ICmpInst::ICMP_UGT : + ICmpInst::ICMP_SGT; + return true; + } + return false; + case FCmpInst::FCMP_OEQ: return false; // Nothing is more precise + case FCmpInst::FCMP_ONE: return false; // Nothing is more precise + case FCmpInst::FCMP_OLT: return false; // Nothing is more precise + case FCmpInst::FCMP_OGT: return false; // Nothing is more precise + case FCmpInst::FCMP_OLE: + if (Op == FCmpInst::FCMP_OEQ || Op == FCmpInst::FCMP_OLT) { + Rel = Op; + return true; + } else if (Op == FCmpInst::FCMP_ONE) { + Rel = FCmpInst::FCMP_OLT; + return true; + } + return false; + case FCmpInst::FCMP_OGE: + return Op == FCmpInst::FCMP_OLT; + if (Op == FCmpInst::FCMP_OEQ || Op == FCmpInst::FCMP_OGT) { + Rel = Op; + return true; + } else if (Op == FCmpInst::FCMP_ONE) { + Rel = FCmpInst::FCMP_OGT; return true; } return false; @@ -1216,28 +1317,67 @@ bool Relation::incorporate(Instruction::BinaryOps Op, ValueInfo &VI) { // determine the result required, return Unknown. // Relation::KnownResult -Relation::getImpliedResult(Instruction::BinaryOps Op) const { +Relation::getImpliedResult(unsigned Op) const { if (Rel == Op) return KnownTrue; - if (Rel == SetCondInst::getInverseCondition(Op)) return KnownFalse; + if (Op >= ICmpInst::FIRST_ICMP_PREDICATE && + Op <= ICmpInst::LAST_ICMP_PREDICATE) { + if (Rel == unsigned(ICmpInst::getInversePredicate(ICmpInst::Predicate(Op)))) + return KnownFalse; + } else if (Op <= FCmpInst::LAST_FCMP_PREDICATE) { + if (Rel == unsigned(FCmpInst::getInversePredicate(FCmpInst::Predicate(Op)))) + return KnownFalse; + } switch (Rel) { default: assert(0 && "Unknown prior value!"); - case Instruction::SetEQ: - if (Op == Instruction::SetLE || Op == Instruction::SetGE) return KnownTrue; - if (Op == Instruction::SetLT || Op == Instruction::SetGT) return KnownFalse; + case ICmpInst::ICMP_EQ: + if (Op == ICmpInst::ICMP_ULE || Op == ICmpInst::ICMP_SLE || + Op == ICmpInst::ICMP_UGE || Op == ICmpInst::ICMP_SGE) return KnownTrue; + if (Op == ICmpInst::ICMP_ULT || Op == ICmpInst::ICMP_SLT || + Op == ICmpInst::ICMP_UGT || Op == ICmpInst::ICMP_SGT) return KnownFalse; + break; + case ICmpInst::ICMP_ULT: + case ICmpInst::ICMP_SLT: + if (Op == ICmpInst::ICMP_ULE || Op == ICmpInst::ICMP_SLE || + Op == ICmpInst::ICMP_NE) return KnownTrue; + if (Op == ICmpInst::ICMP_EQ) return KnownFalse; + break; + case ICmpInst::ICMP_UGT: + case ICmpInst::ICMP_SGT: + if (Op == ICmpInst::ICMP_UGE || Op == ICmpInst::ICMP_SGE || + Op == ICmpInst::ICMP_NE) return KnownTrue; + if (Op == ICmpInst::ICMP_EQ) return KnownFalse; + break; + case FCmpInst::FCMP_OEQ: + if (Op == FCmpInst::FCMP_OLE || Op == FCmpInst::FCMP_OGE) return KnownTrue; + if (Op == FCmpInst::FCMP_OLT || Op == FCmpInst::FCMP_OGT) return KnownFalse; break; - case Instruction::SetLT: - if (Op == Instruction::SetNE || Op == Instruction::SetLE) return KnownTrue; - if (Op == Instruction::SetEQ) return KnownFalse; + case FCmpInst::FCMP_OLT: + if (Op == FCmpInst::FCMP_ONE || Op == FCmpInst::FCMP_OLE) return KnownTrue; + if (Op == FCmpInst::FCMP_OEQ) return KnownFalse; break; - case Instruction::SetGT: - if (Op == Instruction::SetNE || Op == Instruction::SetGE) return KnownTrue; - if (Op == Instruction::SetEQ) return KnownFalse; + case FCmpInst::FCMP_OGT: + if (Op == FCmpInst::FCMP_ONE || Op == FCmpInst::FCMP_OGE) return KnownTrue; + if (Op == FCmpInst::FCMP_OEQ) return KnownFalse; break; - case Instruction::SetNE: - case Instruction::SetLE: - case Instruction::SetGE: - case Instruction::Add: + case ICmpInst::ICMP_NE: + case ICmpInst::ICMP_SLE: + case ICmpInst::ICMP_ULE: + case ICmpInst::ICMP_UGE: + case ICmpInst::ICMP_SGE: + case FCmpInst::FCMP_ONE: + case FCmpInst::FCMP_OLE: + case FCmpInst::FCMP_OGE: + case FCmpInst::FCMP_FALSE: + case FCmpInst::FCMP_ORD: + case FCmpInst::FCMP_UNO: + case FCmpInst::FCMP_UEQ: + case FCmpInst::FCMP_UGT: + case FCmpInst::FCMP_UGE: + case FCmpInst::FCMP_ULT: + case FCmpInst::FCMP_ULE: + case FCmpInst::FCMP_UNE: + case FCmpInst::FCMP_TRUE: break; } return Unknown; @@ -1251,7 +1391,7 @@ Relation::getImpliedResult(Instruction::BinaryOps Op) const { // print - Implement the standard print form to print out analysis information. void CEE::print(std::ostream &O, const Module *M) const { O << "\nPrinting Correlated Expression Info:\n"; - for (std::map::const_iterator I = + for (std::map::const_iterator I = RegionInfoMap.begin(), E = RegionInfoMap.end(); I != E; ++I) I->second.print(O); } @@ -1290,12 +1430,30 @@ void Relation::print(std::ostream &OS) const { OS << " is "; switch (Rel) { default: OS << "*UNKNOWN*"; break; - case Instruction::SetEQ: OS << "== "; break; - case Instruction::SetNE: OS << "!= "; break; - case Instruction::SetLT: OS << "< "; break; - case Instruction::SetGT: OS << "> "; break; - case Instruction::SetLE: OS << "<= "; break; - case Instruction::SetGE: OS << ">= "; break; + case ICmpInst::ICMP_EQ: + case FCmpInst::FCMP_ORD: + case FCmpInst::FCMP_UEQ: + case FCmpInst::FCMP_OEQ: OS << "== "; break; + case ICmpInst::ICMP_NE: + case FCmpInst::FCMP_UNO: + case FCmpInst::FCMP_UNE: + case FCmpInst::FCMP_ONE: OS << "!= "; break; + case ICmpInst::ICMP_ULT: + case ICmpInst::ICMP_SLT: + case FCmpInst::FCMP_ULT: + case FCmpInst::FCMP_OLT: OS << "< "; break; + case ICmpInst::ICMP_UGT: + case ICmpInst::ICMP_SGT: + case FCmpInst::FCMP_UGT: + case FCmpInst::FCMP_OGT: OS << "> "; break; + case ICmpInst::ICMP_ULE: + case ICmpInst::ICMP_SLE: + case FCmpInst::FCMP_ULE: + case FCmpInst::FCMP_OLE: OS << "<= "; break; + case ICmpInst::ICMP_UGE: + case ICmpInst::ICMP_SGE: + case FCmpInst::FCMP_UGE: + case FCmpInst::FCMP_OGE: OS << ">= "; break; } WriteAsOperand(OS, Val); @@ -1303,6 +1461,6 @@ void Relation::print(std::ostream &OS) const { } // Don't inline these methods or else we won't be able to call them from GDB! -void Relation::dump() const { print(std::cerr); } -void ValueInfo::dump() const { print(std::cerr, 0); } -void RegionInfo::dump() const { print(std::cerr); } +void Relation::dump() const { print(*cerr.stream()); } +void ValueInfo::dump() const { print(*cerr.stream(), 0); } +void RegionInfo::dump() const { print(*cerr.stream()); }