Index: lib/Transforms/Scalar/RewriteStatepointsForGC.cpp =================================================================== --- lib/Transforms/Scalar/RewriteStatepointsForGC.cpp +++ lib/Transforms/Scalar/RewriteStatepointsForGC.cpp @@ -1810,54 +1810,21 @@ // Helper function for the "rematerializeLiveValues". It walks use chain // starting from the "CurrentValue" until it meets "BaseValue". Only "simple" -// values are visited (currently it is GEP's and casts). Returns true if it -// successfully reached "BaseValue" and false otherwise. -// Fills "ChainToBase" array with all visited values. "BaseValue" is not -// recorded. -static bool findRematerializableChainToBasePointer( +// values are visited (currently it is GEP's and casts). Returns the Root of the +// chain if it successfully reached "BaseValue" and null otherwise. Fills +// "ChainToBase" array with all visited values. "BaseValue" is not recorded. +static Value* findRematerializableChainToBasePointer( SmallVectorImpl &ChainToBase, Value *CurrentValue, Value *BaseValue) { // We have found a base value - if (CurrentValue == BaseValue) { - return true; - } - - // Check for same values, when both BaseValue and CurrentValue are phi nodes. - // PHI nodes that have the same incoming values, and belonging to the same - // basic blocks are essentially the same SSA value. Such an example of same - // BaseValue, CurrentValue phis is created by findBasePointer, when a phi has - // incoming values with different base pointers. This phi is marked as - // conflict, and hence an additional phi with the same incoming values get - // generated. We need to identify the BaseValue (.base version of phi) and - // CurrentValue (the phi node itself) as the same, so that we can - // rematerialize the gep and casts below. This is a workaround for the - // deficieny in the findBasePointer algorithm. - if (PHINode *CurrentPhi = dyn_cast(CurrentValue)) - if (PHINode *BasePhi = dyn_cast(BaseValue)) { - auto PhiNum = CurrentPhi->getNumIncomingValues(); - if (PhiNum != BasePhi->getNumIncomingValues() || - CurrentPhi->getParent() != BasePhi->getParent()) - return false; - // Map of incoming values and their corresponding basic blocks of - // CurrentPhi. - SmallDenseMap CurrentIncomingValues; - for (unsigned i = 0; i < PhiNum; i++) - CurrentIncomingValues[CurrentPhi->getIncomingValue(i)] = - CurrentPhi->getIncomingBlock(i); + if (CurrentValue == BaseValue) + return CurrentValue; - // Both current and base PHIs should have same incoming values and - // the same basic blocks corresponding to the incoming values. - for (unsigned i = 0; i < PhiNum; i++) { - auto CIVI = CurrentIncomingValues.find(BasePhi->getIncomingValue(i)); - if (CIVI == CurrentIncomingValues.end()) - return false; - BasicBlock *CurrentIncomingBB = CIVI->second; - if (CurrentIncomingBB != BasePhi->getIncomingBlock(i)) - return false; - } - return true; - } + // If both are phi nodes, we check if the incoming values of the phi nodes are + // the same (i.e. they are same SSA values) at the caller side. + if (isa(CurrentValue) && isa(BaseValue)) + return CurrentValue; if (GetElementPtrInst *GEP = dyn_cast(CurrentValue)) { ChainToBase.push_back(GEP); @@ -1868,7 +1835,7 @@ if (CastInst *CI = dyn_cast(CurrentValue)) { if (!CI->isNoopCast(CI->getModule()->getDataLayout())) - return false; + return nullptr; ChainToBase.push_back(CI); return findRematerializableChainToBasePointer(ChainToBase, @@ -1876,7 +1843,7 @@ } // Not supported instruction in the chain - return false; + return nullptr; } // Helper function for the "rematerializeLiveValues". Compute cost of the use @@ -1930,16 +1897,70 @@ // For each live pointer find it's defining chain SmallVector ChainToBase; assert(Info.PointerToBase.count(LiveValue)); - bool FoundChain = + Value *RootNode = findRematerializableChainToBasePointer(ChainToBase, LiveValue, Info.PointerToBase[LiveValue]); // Nothing to do, or chain is too long - if (!FoundChain || + if (!RootNode || ChainToBase.size() == 0 || ChainToBase.size() > ChainLengthThreshold) continue; + // The only scenario where returned root node is not equal to the base + // pointer (original root node) is when both are phi nodes. + if (RootNode != Info.PointerToBase[LiveValue]) { + // Check for same values, when both BaseValue and RootNode are phi nodes. + // PHI nodes that have the same incoming values, and belonging to the same + // basic blocks are essentially the same SSA value. Such an example of + // same BaseValue, RootNode phis is created by findBasePointer, when a phi + // has incoming values with different base pointers. This phi is marked as + // conflict, and hence an additional phi with the same incoming values get + // generated. We need to identify the newly generated AlternateRootPhi + // (.base version of phi) and RootNode (the original phi node itself) as + // the same, so that we can rematerialize the gep and casts below. This is + // a workaround for the deficieny in the findBasePointer algorithm. + PHINode *OrigRootPhi = cast(RootNode); + PHINode *AlternateRootPhi = cast(Info.PointerToBase[LiveValue]); + + auto AreSameIncomingValues = + [](unsigned &PhiNum, + SmallDenseMap &CurrentIncomingValues, + PHINode &AlternateRootPhi) { + + for (unsigned i = 0; i < PhiNum; i++) { + auto CIVI = + CurrentIncomingValues.find(AlternateRootPhi.getIncomingValue(i)); + if (CIVI == CurrentIncomingValues.end()) + return false; + BasicBlock *CurrentIncomingBB = CIVI->second; + if (CurrentIncomingBB != AlternateRootPhi.getIncomingBlock(i)) + return false; + } + return true; + + }; + unsigned PhiNum = OrigRootPhi->getNumIncomingValues(); + if (PhiNum != AlternateRootPhi->getNumIncomingValues() || + OrigRootPhi->getParent() != AlternateRootPhi->getParent()) + continue; + // Map of incoming values and their corresponding basic blocks of + // OrigRootPhi. + SmallDenseMap CurrentIncomingValues; + for (unsigned i = 0; i < PhiNum; i++) + CurrentIncomingValues[OrigRootPhi->getIncomingValue(i)] = + OrigRootPhi->getIncomingBlock(i); + + // Both current and base PHIs should have same incoming values and + // the same basic blocks corresponding to the incoming values. + if (!AreSameIncomingValues(PhiNum, CurrentIncomingValues, + *AlternateRootPhi)) + continue; + // Now that the phi nodes are proved to be the same, assert that + // findBasePointer's newly generated AlternateRootPhi is present in the + // liveset of the call. + assert(Info.LiveSet.count(AlternateRootPhi)); + } // Compute cost of this chain unsigned Cost = chainToBasePointerCost(ChainToBase, TTI); // TODO: We can also account for cases when we will be able to remove some