37#ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
38#define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
49#define DEBUG_TYPE "dom-tree-builder"
52namespace DomTreeBuilder {
54template <
typename DomTreeT>
56 using NodePtr =
typename DomTreeT::NodePtr;
57 using NodeT =
typename DomTreeT::NodeType;
59 using RootsT =
decltype(DomTreeT::Roots);
60 static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
78 using UpdateT =
typename DomTreeT::UpdateType;
107 template <
bool Inversed>
110 return BUI->
PreViewCFG.template getChildren<Inversed>(
N);
111 return getChildren<Inversed>(
N);
114 template <
bool Inversed>
116 using DirectedNodeT =
117 std::conditional_t<Inversed, Inverse<NodePtr>,
NodePtr>;
118 auto R = children<DirectedNodeT>(
N);
128 if (InfoIt ==
NodeToInfo.end())
return nullptr;
130 return InfoIt->second.IDom;
140 assert(IDom || DT.DomTreeNodes[
nullptr]);
145 return DT.createChild(BB, IDomNode);
160 BP.
N->printAsOperand(O,
false);
178 template <
bool IsReverse = false,
typename DescendCondition>
180 unsigned AttachToNum,
186 while (!WorkList.
empty()) {
189 BBInfo.ReverseChildren.push_back(ParentNum);
192 if (BBInfo.DFSNum != 0)
continue;
193 BBInfo.Parent = ParentNum;
194 BBInfo.DFSNum = BBInfo.Semi = BBInfo.Label = ++LastNum;
198 auto Successors = getChildren<Direction>(BB,
BatchUpdates);
199 if (SuccOrder && Successors.size() > 1)
202 return SuccOrder->find(A)->second < SuccOrder->find(B)->second;
205 for (
const NodePtr Succ : Successors) {
206 if (!Condition(BB, Succ))
continue;
228 unsigned eval(
unsigned V,
unsigned LastLinked,
232 if (VInfo->
Parent < LastLinked)
238 Stack.push_back(VInfo);
239 VInfo = NumToInfo[VInfo->
Parent];
240 }
while (VInfo->
Parent >= LastLinked);
247 VInfo = Stack.pop_back_val();
250 if (PLabelInfo->
Semi < VLabelInfo->
Semi)
253 PLabelInfo = VLabelInfo;
255 }
while (!Stack.empty());
265 for (
unsigned i = 1; i < NextDFSNum; ++i) {
274 for (
unsigned i = NextDFSNum - 1; i >= 2; --i) {
275 auto &WInfo = *NumToInfo[i];
278 WInfo.Semi = WInfo.Parent;
279 for (
unsigned N : WInfo.ReverseChildren) {
280 unsigned SemiU = NumToInfo[
eval(
N, i + 1, EvalStack, NumToInfo)]->Semi;
281 if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;
289 for (
unsigned i = 2; i < NextDFSNum; ++i) {
290 auto &WInfo = *NumToInfo[i];
292 const unsigned SDomNum = NumToInfo[WInfo.Semi]->DFSNum;
293 NodePtr WIDomCandidate = WInfo.IDom;
295 auto &WIDomCandidateInfo =
NodeToInfo.find(WIDomCandidate)->second;
296 if (WIDomCandidateInfo.DFSNum <= SDomNum)
298 WIDomCandidate = WIDomCandidateInfo.IDom;
301 WInfo.IDom = WIDomCandidate;
315 BBInfo.DFSNum = BBInfo.Semi = BBInfo.Label = 1;
324 assert(
N &&
"N must be a valid node");
325 return !getChildren<false>(
N, BUI).empty();
329 assert(DT.Parent &&
"Parent not set");
337 assert(DT.Parent &&
"Parent pointer is not set");
381 bool HasNonTrivialRoots =
false;
384 if (
Total + 1 != Num) {
385 HasNonTrivialRoots =
true;
392 std::optional<NodeOrderMap> SuccOrder;
393 auto InitSuccOrderOnce = [&]() {
398 SuccOrder->try_emplace(Succ, 0);
401 unsigned NodeNum = 0;
402 for (
const auto Node :
nodes(DT.Parent)) {
404 auto Order = SuccOrder->find(
Node);
405 if (Order != SuccOrder->end()) {
406 assert(Order->second == 0);
407 Order->second = NodeNum;
439 const unsigned NewNum =
443 <<
"(non-trivial root): "
445 Roots.push_back(FurthestAway);
446 LLVM_DEBUG(
dbgs() <<
"\t\t\tPrev DFSNum: " << Num <<
", new DFSNum: "
447 << NewNum <<
"\n\t\t\tRemoving DFS info\n");
448 for (
unsigned i = NewNum; i > Num; --i) {
455 const unsigned PrevNum = Num;
458 for (
unsigned i = PrevNum + 1; i <= Num; ++i)
470 assert((
Total + 1 == Num) &&
"Everything should have been visited");
499 for (
unsigned i = 0; i < Roots.size(); ++i) {
500 auto &Root = Roots[i];
504 <<
" remains a root\n");
510 for (
unsigned x = 2; x <= Num; ++x) {
531 template <
typename DescendCondition>
534 assert(DT.Roots.size() == 1 &&
"Dominators should have a singe root");
535 runDFS(DT.Roots[0], 0, DC, 0);
541 for (
const NodePtr Root : DT.Roots) Num =
runDFS(Root, Num, DC, 1);
545 auto *Parent = DT.Parent;
569 dbgs() <<
"DomTree recalculated, skipping future batch updates\n");
572 if (DT.Roots.empty())
return;
579 DT.RootNode = DT.createNode(Root);
589 if (DT.DomTreeNodes[W])
continue;
598 DT.createChild(W, IDomNode);
616 return LHS->getLevel() <
RHS->getLevel();
622 std::priority_queue<TreeNodePtr, SmallVector<TreeNodePtr, 8>,
627#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
635 "From has to be a valid CFG node or a virtual root");
636 assert(To &&
"Cannot be a nullptr");
647 FromTN = DT.createChild(
From, VirtualRoot);
648 DT.Roots.push_back(
From);
651 DT.DFSInfoValid =
false;
668 if (!DT.isVirtualRoot(To->
getIDom()))
return false;
674 <<
" is no longer a root\n\t\tRebuilding the tree!!!\n");
682 if (
A.size() !=
B.size())
699 return HasForwardSuccessors(N, BUI);
712 <<
"The entire tree needs to be rebuilt\n");
730 ? DT.findNearestCommonDominator(
From->getBlock(), To->
getBlock())
732 assert(NCDBlock || DT.isPostDominator());
737 const unsigned NCDLevel = NCD->
getLevel();
755 II.Visited.insert(To);
757 while (!
II.Bucket.empty()) {
760 II.Affected.push_back(TN);
762 const unsigned CurrentLevel = TN->
getLevel();
764 "as affected, CurrentLevel " << CurrentLevel <<
"\n");
777 for (
const NodePtr Succ : getChildren<IsPostDom>(TN->
getBlock(), BUI)) {
780 "Unreachable successor found at reachable insertion");
781 const unsigned SuccLevel = SuccTN->
getLevel();
784 <<
", level = " << SuccLevel <<
"\n");
793 if (SuccLevel <= NCDLevel + 1 || !
II.Visited.insert(SuccTN).second)
796 if (SuccLevel > CurrentLevel) {
801 UnaffectedOnCurrentLevel.
push_back(SuccTN);
803 II.VisitedUnaffected.push_back(SuccTN);
809 <<
" to a Bucket\n");
810 II.Bucket.push(SuccTN);
814 if (UnaffectedOnCurrentLevel.
empty())
836#if defined(LLVM_ENABLE_ABI_BREAKING_CHECKS) && !defined(NDEBUG)
839 "TN should have been updated by an affected ancestor");
862 for (
const auto &Edge : DiscoveredEdgesToReachable) {
875 &DiscoveredConnectingEdges) {
876 assert(!DT.getNode(Root) &&
"Root must not be reachable");
879 auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](
NodePtr From,
882 if (!ToTN)
return true;
884 DiscoveredConnectingEdges.push_back({
From, ToTN});
889 SNCA.
runDFS(Root, 0, UnreachableDescender, 0);
898 assert(
From && To &&
"Cannot disconnect nullptrs");
902#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
906 auto IsSuccessor = [BUI](
const NodePtr SuccCandidate,
const NodePtr Of) {
907 auto Successors = getChildren<IsPostDom>(Of, BUI);
911 assert(!IsSuccessor(To,
From) &&
"Deleted edge still exists in the CFG!");
922 <<
") already unreachable -- there is no edge to delete\n");
926 const NodePtr NCDBlock = DT.findNearestCommonDominator(
From, To);
931 DT.DFSInfoValid =
false;
960 assert(ToIDom || DT.isPostDominator());
966 if (!PrevIDomSubTree) {
973 const unsigned Level = ToIDomTN->
getLevel();
975 return DT.getNode(To)->getLevel() > Level;
982 SNCA.
runDFS(ToIDom, 0, DescendBelow, 0);
995 for (
const NodePtr Pred : getChildren<!IsPostDom>(TNB, BUI)) {
997 if (!DT.getNode(Pred))
continue;
999 const NodePtr Support = DT.findNearestCommonDominator(TNB, Pred);
1001 if (Support != TNB) {
1003 <<
" is reachable from support "
1025 LLVM_DEBUG(
dbgs() <<
"\tDeletion made a region reverse-unreachable\n");
1028 DT.Roots.push_back(ToTN->
getBlock());
1034 const unsigned Level = ToTN->
getLevel();
1038 auto DescendAndCollect = [Level, &AffectedQueue, &DT](
NodePtr,
NodePtr To) {
1041 if (TN->
getLevel() > Level)
return true;
1049 unsigned LastDFSNum =
1056 for (
const NodePtr N : AffectedQueue) {
1060 assert(NCDBlock || DT.isPostDominator());
1079 for (
unsigned i = LastDFSNum; i > 0; --i) {
1088 if (MinNode == ToTN)
return;
1090 LLVM_DEBUG(
dbgs() <<
"DeleteUnreachable: running DFS with MinNode = "
1092 const unsigned MinLevel = MinNode->
getLevel();
1100 return ToTN && ToTN->
getLevel() > MinLevel;
1121 assert(ChIt != IDom->Children.end());
1122 std::swap(*ChIt, IDom->Children.back());
1123 IDom->Children.pop_back();
1125 DT.DomTreeNodes.erase(TN->
getBlock());
1137 if (NumUpdates == 0)
1142 if (NumUpdates == 1) {
1145 if (Update.getKind() == UpdateKind::Insert)
1146 InsertEdge(DT,
nullptr, Update.getFrom(), Update.getTo());
1148 DeleteEdge(DT,
nullptr, Update.getFrom(), Update.getTo());
1151 if (Update.getKind() == UpdateKind::Insert)
1152 InsertEdge(DT, &BUI, Update.getFrom(), Update.getTo());
1154 DeleteEdge(DT, &BUI, Update.getFrom(), Update.getTo());
1168 if (DT.DomTreeNodes.size() <= 100) {
1171 }
else if (BUI.
NumLegalized > DT.DomTreeNodes.size() / 40)
1192 if (CurrentUpdate.getKind() == UpdateKind::Insert)
1193 InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1195 DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1208 if (!DT.Parent && !DT.Roots.empty()) {
1209 errs() <<
"Tree has no parent but has roots!\n";
1215 if (DT.Roots.empty()) {
1216 errs() <<
"Tree doesn't have a root!\n";
1222 errs() <<
"Tree's root is not its parent's entry node!\n";
1230 errs() <<
"Tree has different roots than freshly computed ones!\n";
1231 errs() <<
"\tPDT roots: ";
1233 errs() <<
"\n\tComputed roots: ";
1234 for (
const NodePtr N : ComputedRoots)
1250 for (
auto &NodeToTN : DT.DomTreeNodes) {
1255 if (DT.isVirtualRoot(TN))
continue;
1259 <<
" not found by DFS walk!\n";
1267 if (
N && !DT.getNode(
N)) {
1269 <<
" not found in the DomTree!\n";
1283 for (
auto &NodeToTN : DT.DomTreeNodes) {
1289 if (!IDom && TN->
getLevel() != 0) {
1291 <<
" has a nonzero level " << TN->
getLevel() <<
"!\n";
1299 << TN->
getLevel() <<
" while its IDom "
1315 if (!DT.DFSInfoValid || !DT.Parent)
1321 auto PrintNodeAndDFSNums = [](
const TreeNodePtr TN) {
1323 << TN->getDFSNumOut() <<
'}';
1329 errs() <<
"DFSIn number for the tree root is not:\n\t";
1330 PrintNodeAndDFSNums(Root);
1338 for (
const auto &NodeToTN : DT.DomTreeNodes) {
1342 if (
Node->isLeaf()) {
1343 if (
Node->getDFSNumIn() + 1 !=
Node->getDFSNumOut()) {
1344 errs() <<
"Tree leaf should have DFSOut = DFSIn + 1:\n\t";
1345 PrintNodeAndDFSNums(
Node);
1361 auto PrintChildrenError = [
Node, &Children, PrintNodeAndDFSNums](
1365 errs() <<
"Incorrect DFS numbers for:\n\tParent ";
1366 PrintNodeAndDFSNums(
Node);
1368 errs() <<
"\n\tChild ";
1369 PrintNodeAndDFSNums(FirstCh);
1372 errs() <<
"\n\tSecond child ";
1373 PrintNodeAndDFSNums(SecondCh);
1376 errs() <<
"\nAll children: ";
1378 PrintNodeAndDFSNums(Ch);
1386 if (Children.front()->getDFSNumIn() !=
Node->getDFSNumIn() + 1) {
1387 PrintChildrenError(Children.front(),
nullptr);
1391 if (Children.back()->getDFSNumOut() + 1 !=
Node->getDFSNumOut()) {
1392 PrintChildrenError(Children.back(),
nullptr);
1396 for (
size_t i = 0, e = Children.size() - 1; i != e; ++i) {
1397 if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) {
1398 PrintChildrenError(Children[i], Children[i + 1]);
1451 for (
auto &NodeToTN : DT.DomTreeNodes) {
1461 return From != BB && To != BB;
1465 if (
NodeToInfo.count(Child->getBlock()) != 0) {
1468 <<
" is removed!\n";
1485 for (
auto &NodeToTN : DT.DomTreeNodes) {
1495 return From != BBN && To != BBN;
1499 if (S ==
N)
continue;
1504 <<
" is removed!\n";
1525 FreshTree.recalculate(*DT.Parent);
1526 const bool Different = DT.compare(FreshTree);
1529 errs() << (DT.isPostDominator() ?
"Post" :
"")
1530 <<
"DominatorTree is different than a freshly computed one!\n"
1533 errs() <<
"\n\tFreshly computed tree:\n";
1534 FreshTree.print(
errs());
1542template <
class DomTreeT>
1547template <
typename DomTreeT>
1558template <
class DomTreeT>
1560 typename DomTreeT::NodePtr To) {
1565template <
class DomTreeT>
1567 typename DomTreeT::NodePtr To) {
1572template <
class DomTreeT>
1575 DomTreeT::IsPostDominator> &PreViewCFG,
1577 DomTreeT::IsPostDominator> *PostViewCFG) {
1581template <
class DomTreeT>
1582bool Verify(
const DomTreeT &DT,
typename DomTreeT::VerificationLevel VL) {
1596 if (VL == DomTreeT::VerificationLevel::Basic ||
1597 VL == DomTreeT::VerificationLevel::Full)
1600 if (VL == DomTreeT::VerificationLevel::Full)
Unify divergent function exit nodes
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file defines the DenseSet and SmallDenseSet classes.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
This file defines a set of templates that efficiently compute a dominator tree over a generic graph.
Loop::LoopBounds::Direction Direction
uint64_t IntrinsicInst * II
ppc ctr loops PowerPC CTR Loops Verify
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Base class for the actual dominator tree node.
iterator_range< iterator > children()
void setIDom(DomTreeNodeBase *NewIDom)
DomTreeNodeBase * getIDom() const
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
size_t getNumChildren() const
unsigned getLevel() const
cfg::Update< NodePtr > popUpdateForIncrementalUpdates()
unsigned getNumLegalizedUpdates() const
Implements a dense probed hash-table based set with some number of buckets stored inline.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void reserve(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This class implements an extremely fast bulk output stream that can only output to a stream.
void CalculateWithUpdates(DomTreeT &DT, ArrayRef< typename DomTreeT::UpdateType > Updates)
void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
void Calculate(DomTreeT &DT)
void ApplyUpdates(DomTreeT &DT, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > &PreViewCFG, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > *PostViewCFG)
void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
BatchUpdateInfo(GraphDiffT &PreViewCFG, GraphDiffT *PostViewCFG=nullptr)
const size_t NumLegalized
friend raw_ostream & operator<<(raw_ostream &O, const BlockNamePrinter &BP)
BlockNamePrinter(NodePtr Block)
BlockNamePrinter(TreeNodePtr TN)
SmallVector< unsigned, 4 > ReverseChildren
bool operator()(TreeNodePtr LHS, TreeNodePtr RHS) const
std::priority_queue< TreeNodePtr, SmallVector< TreeNodePtr, 8 >, Compare > Bucket
SmallVector< TreeNodePtr, 8 > Affected
SmallDenseSet< TreeNodePtr, 8 > Visited
NodePtr getIDom(NodePtr BB) const
SemiNCAInfo(BatchUpdatePtr BUI)
static SmallVector< NodePtr, 8 > getChildren(NodePtr N)
static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr NCD, InsertionInfo &II)
static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr From, const NodePtr To)
void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC)
DenseMap< NodePtr, unsigned > NodeOrderMap
static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI)
static SmallVector< NodePtr, 8 > getChildren(NodePtr N, BatchUpdatePtr BUI)
static void ComputeUnreachableDominators(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root, const TreeNodePtr Incoming, SmallVectorImpl< std::pair< NodePtr, TreeNodePtr > > &DiscoveredConnectingEdges)
static bool VerifyLevels(const DomTreeT &DT)
decltype(DomTreeT::Roots) RootsT
bool verifyReachability(const DomTreeT &DT)
unsigned eval(unsigned V, unsigned LastLinked, SmallVectorImpl< InfoRec * > &Stack, ArrayRef< InfoRec * > NumToInfo)
static bool IsSameAsFreshTree(const DomTreeT &DT)
static void EraseNode(DomTreeT &DT, const TreeNodePtr TN)
static constexpr bool IsPostDom
typename DomTreeT::NodePtr NodePtr
static void ApplyUpdates(DomTreeT &DT, GraphDiffT &PreViewCFG, GraphDiffT *PostViewCFG)
typename DomTreeT::UpdateKind UpdateKind
static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const TreeNodePtr To)
bool verifySiblingProperty(const DomTreeT &DT)
typename DomTreeT::NodeType NodeT
void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo)
static NodePtr GetEntryNode(const DomTreeT &DT)
static bool AlwaysDescend(NodePtr, NodePtr)
static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI)
SmallVector< NodePtr, 64 > NumToNode
unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition, unsigned AttachToNum, const NodeOrderMap *SuccOrder=nullptr)
static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr FromTN, const TreeNodePtr ToTN)
static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI, RootsT &Roots)
static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr TN)
static bool isPermutation(const SmallVectorImpl< NodePtr > &A, const SmallVectorImpl< NodePtr > &B)
static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI)
TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT)
typename DomTreeT::UpdateType UpdateT
static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const TreeNodePtr To)
static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI)
static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const NodePtr To)
static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI)
DenseMap< NodePtr, InfoRec > NodeToInfo
static bool VerifyDFSNumbers(const DomTreeT &DT)
static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr ToTN)
void attachNewSubtree(DomTreeT &DT, const TreeNodePtr AttachTo)
static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr From, const NodePtr To)
BatchUpdateInfo * BatchUpdates
bool verifyParentProperty(const DomTreeT &DT)
bool verifyRoots(const DomTreeT &DT)
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...