// MDlink.bcpl -- setup branch linkages
// last edited July 5, 1980  9:05 AM

	get "mddecl.d"

external [	// defined here
	Link	// (zone)
]

external [
		// OS
	Allocate
		// MicroD
	@IP
	Err
	PutAddress
	@DMachine
	@IM; @SaveW2; @NInstructions; @IMMASK
		// MDmake
	MakePlus1; MakePageLink; MakeSubpageLink
		// MDprescan
	@globalZero; @nGlobalPages
	@ifuMask
	@calledMask; @goedtoMask; @jbctMask
	@callerMask; @slowJump; @jbcSubpage
]

//This procedure begins with the data structure left by Load, which
//describes what each instruction does (GOTO, CALL, BRANCH, RETURN,
//or CORETURN).  It builds the linkages and other information which
//will be needed by the various allocation procedures that execute
//later as follows:
//  1.	Propagates IFU entry restriction from IFU entries to the
//	target instructions.
//  2.	Propagates GOTO-target and CALL-target information from
//	goers to goees and callers to callees.
//  3.	Propagates xor1 constraints to targets of conditional jumps.
//  4.	Points jbc instructions at their targets.
//  5.	Points other branches at their targets.
//All the above information is encoded in a mask which represents
//possible locations of the instruction within a group of 20B;
//the bLink and aLink pointers as described in MDmake; and the
//jbcLinked, onPage, atWord, global, and IFUE flags and W0 field
//as described in MDdecl.d.

// Note that Link assumes that Scan has already done a lot of
// constraint checking

let Link(zone) be
[	Err(PassMessage,"Linking...")
//Reset mask and link fields
//For D0, propagate page switches
	let nGlobal, nW2 = 0, 0
	let z = (DMachine eq 0? -1, 0)
	for i = 0 to NInstructions-1 do
	[ let ip = IP(i)
// Tally # of W2 references
	  if ip>>IM.W2 ne i+1 then nW2 = nW2+1
// Propagate swpage to target's successor's page
	  if (DMachine eq 0) & (ip>>IM.swpage ne 0) then
	  [ let i1 = ip>>IM.W1
	    let ip1 = IP(i1)
	    let i2 = (slowJump? ip1>>IM.W1, i1)
	    if i2 ne WExt then
	    [ let ip2 = IP(i2)
	      let newpage = ip>>IM.newpage lshift 8
	      ip2>>IM.W0, ip2>>IM.onPage = (ip2>>IM.W0&377B)+newpage, 1
	    ]
	  ]
// Initialize mask
	  ip>>IM.Linkinit = i	// null aLink, not on any +1 list
	  let mask = -1
	  if ip>>IM.IFUE ne 0 then
	   test ip>>IM.IFUseq eq 0
	    ifso mask = ifuMask
	    ifnot
	    [ ip>>IM.IFUE, ip>>IM.IFUseq = 0, 0
	      MakePlus1(i-1, i)	// IFU sequence -- aLink already initialized
	    ]
	  test ip>>IM.atW0
	  ifso
	  [ mask, ip>>IM.onPage, ip>>IM.atWord =
	      mask & (100000b rshift (ip>>IM.W0 & 17b)), 1, 1
	    if (ip>>IM.W0 & globalZero) eq z then
	    [ ip>>IM.global = 1
	      nGlobal = nGlobal+1
	    ]
	  ]
	  ifnot test (ip>>IM.global ne 0) & (DMachine ne 0)
	  ifso
	  [ mask, ip>>IM.W0, ip>>IM.atWord =
	      mask & globalMask, ip>>IM.W0 & not 77b, 1
	    nGlobal = nGlobal+1
	  ]
	  ifnot
	  [ ip>>IM.atWord = 0
	    if DMachine eq 0 then
	     test ip>>IM.calls
	      ifso mask = mask & callerMask
	      ifnot
	     if ip>>IM.oddcall then mask = mask & oddMask
	  ]
	  ip>>IM.mask = mask
	]
// Check global constraints
	if nGlobal gr nGlobalPages then Err(PassFatal, "More than $D GLOBAL entries", nGlobalPages)
// Put targets of conditionals and successors of calls on +1 lists
// (Done first so we can re-use the W2 field for bLink)
	SaveW2 = Allocate(zone, 2*nW2+1)
	let swp = SaveW2
	for i = 0 to NInstructions-1 do
	[ let Iptr = IP(i)
	  let W2 = Iptr>>IM.W2
	  if W2 ne i+1 then [ @swp, swp!1 = i, W2; swp = swp+2 ]
	  Iptr>>IM.bLink = i	// (overlays W2)
	  test Iptr>>IM.iscond
	   ifso
	  [ MakePlus1(Iptr>>IM.W1, W2)
	    if Iptr>>IM.calls then	// DblCall, W2 unavailable for return address
	      MakePlus1(i, i+1)
	  ]
	   ifnot
	  if Iptr>>IM.calls ne 0 then
	    MakePlus1(i, W2)
	]
//Establish linkages by scan of IM
	let JbcLink = (jbcSubpage? MakeSubpageLink, MakePageLink)
	for i = 0 to NInstructions-1 do
	[ let Iptr = IP(i)
	  let W1 = Iptr>>IM.W1
	  if W1 eq WExt loop
	  let W1ptr = IP(W1)
// Mark target of conditionals
	  if Iptr>>IM.iscond then
	  [ W1ptr>>IM.mask = W1ptr>>IM.mask & evenMask
	  ]
	  if DMachine eq 0 then
	  [ if (Iptr>>IM.returns eq 0) & (Iptr>>IM.longgo eq 0) then
	      MakePageLink(i, W1)
	    loop
	  ]
// Propagate placement restrictions to callees and goees
	  test Iptr>>IM.goes ifso
	  [ W1ptr>>IM.mask = W1ptr>>IM.mask & goedtoMask
	  ]
	  ifnot if Iptr>>IM.calls then
	  [ unless Iptr>>IM.returns do	// CORETURN
	      W1ptr>>IM.mask = W1ptr>>IM.mask & calledMask
	  ]
//Merge the source and target into a common circular list through bLink.
//The bLink pointer is needed unless
//the instruction returns (W1 irrelevant) or does an unconditional
//long GOTO/CALL, or W1 is a global.
	  test Iptr>>IM.jbc ifso
	  [ W1ptr>>IM.mask = W1ptr>>IM.mask & jbctMask
	    JbcLink(i, W1)
	  ]
	  ifnot
	  [ if (Iptr>>IM.returns eq 0) & (W1ptr>>IM.global eq 0) &
	      ((Iptr>>IM.usesFN ne 0) % (Iptr>>IM.iscond ne 0))
	     then
	      MakePageLink(i, W1)
	  ]
	]
	@swp = 7777B
// Process explicit mask and +1 constraints from IMMASK
	let m = IMMASK
	until m eq 0 do
	[ let i = m>>IMMASK.addr
	  let ip = IP(i)
	  ip>>IM.mask = ip>>IM.mask & m>>IMMASK.mask
	  for j = 1 to m>>IMMASK.nseq do
	  [ MakePlus1(i, i+1)
	    i = i+1
	  ]
	  m = m>>IMMASK.next
	]
]