Software: nginx/1.23.4. PHP/5.6.40-65+ubuntu20.04.1+deb.sury.org+1 

uname -a: Linux foro-restaurado-2 5.15.0-1040-oracle #46-Ubuntu SMP Fri Jul 14 21:47:21 UTC 2023
aarch64 

uid=33(www-data) gid=33(www-data) groups=33(www-data) 

Safe-mode: OFF (not secure)

/home/scripts/pba/phc-read-only/misc/old_comments/   drwxrwxr-x
Free 83.36 GB of 96.73 GB (86.19%)
                            Encoder    Tools    Proc.    FTP brute    Sec.    SQL    PHP-code    Update    Feedback    Self remove    Logout    

Viewing file:     old_hssa_comments.txt (13.21 KB)      -rw-rw-r--

From top of HSSA.cpp:

/*
 * Chow96: "Effective Representation of Aliases and Indirect Memory Operations
 * in SSA Form"; Fred Chow, Sun Chan, Shin-Ming Liu, Raymond Lo, Mark Streich;
 * CC 96.
 */


/*
 * How to convert into HSSA form algorithm 2 from "Effective Representation
 * of Aliases and Indirect Memory Operations in SSA Form", by Chow et al.
 *
 * 1) Assign virtual variables to indirect variables in the program
 *
 * 2)	Perform alias analysis and insert MU and CHI for all scalar and
 *		virtual variables
 *
 * 3) Insert PHIs using Cytron algorithm, including CHI as assignments
 *
 * 4) Rename all scalar and virtual variables using Cytron algorithm
 *
 *
 * We ignore steps 5, 6, 7 and 8. 5 and 6 create zero versions in order to
 * reduce the memory usage of the implementation. That doesnt bother us (at
 * least for now). Steps 7 and 8 perform the global value numbering. While we
 * do wish to have GVN, they also convert it into HSSA form, which actually
 * isnt that interesting, as the only real advantage is how compact it is, and
 * we dont care about that (for now).
 *
 * 5) Simultaneously:
 *		a)	Perform DCE, including on PHIs and CHIs, using Cytron algorithm
 *		b)	Perform steps 1 and 2 of algorithm 1 (Compute Zero Versions), to set
 *			the HasRealOcc flag for all variable versions. These steps are:
 *				czv1)	Initialize flag HasRealOcc for each variable version created
 *						by SSA renaming to false.
 *				czv2)	Pass over the program. On visiting a real occurrence, set
 *						the HasRealOcc flag for the variable version to true.
 *
 *	6)	Performs steps 3, 4 and 5 of CZV algorithm to set variable versions to
 *		0. These steps are:
 *		czv3)	For each program varaible, create NonZeroPhiList and init to
 *				empty.
 *		czv4)	Iterate through all variable versions:
 *				a)	If HasRealOcc is false, and is defined by CHI, set version to 0
 *				b) If HasRealOcc is false, and is defined by PHI:
 *					-	If the version of one of the operands is 0, set version to 0
 *					-	Else if HasRealOcc flag of all operand is set to true, set
 *						HasRealOcc to true
 *					-	Else add version to NonZeroPhiList for the variable
 *		czv5)	For each program variable, iterate until its NonZeroPhiList no
 *				longer changes:
 *				a)	For each version in NonZeroPhiList
 *					-	If the version of one of the operands in 0, set version to 0
 *						and remove from NonZeroPhiList
 *					-	Else if the HasRealOcc flag of all operands is true, set
 *						HasRealOcc to true and remove from NonZeroPhiList
 *
 *	7)	Hash a unique value number and create the corresponding hash table VAR
 *		node for each scalar and virtual variable version that are determined to
 *		be live in Step 5a.
 *
 *	8) Conduct a pre-order traversal of the dominator tree of the control flow
 *		graph of the program and apply global value numbering to the code in
 *		each basic_block:
 *		a)	Hash expression trees bottom-up into the hash-table, searching for
 *			any existing matching entry before creating each new value number
 *			and entry.  At a VAR node, use the node created in step 7 for that
 *			variable version.
 *		b)	For two IVAR nodes to match, two conditions must be satisfied:
 *			1) Their address expressions have the same value number, and
 *			2) the versions of their virtual variables are either the same, or
 *				are separated by definitions that do not alias with the IVAR.
 *		c)	For each assignment statement, including PHI and CHI, represent its
 *			lhs by making the statement point to the VAR or IVAR for direct and
 *			indirect assignments respectively. Also make the VAR or IVAR node
 *			point back to its defining statement.
 *		d)	Update all PHI, MU and CHI operands and results to make them refer
 *			to entries in the hash-table.
 */

From convert_to_hssa_form () in HSSA.cpp:

	// A particular version of a virtual-variable can have only 1 value,
	// maintaining the single-value per defintion rule. If you have
	//		v(*p) = 5;
	//	and then
	//		$x = v(*p);
	//	then 5 can be propagated to $x.
	//
	// The chi's make note of the new version so that this property is
	// maintained, and the mu's extend the live ranges of the definition so
	// that assignments arent killed when they are still in use.
	//
	// A virtual variable represents an 'indirect variable', which can refer to
	// many memory locations:
	//
	//		in C:
	//			*p
	//			*(p+1)
	//			**p
	//			p->next
	//			a[i]
	//
	//		in PHP:
	//			$a[$i]
	//			$$a
	//			$p->next
	//			$p->$f
	//
	//
	//
	// The virtual variables do not remove the requirement for a mu/chi
	// variable at each load/store, for each variable in the alias set at that
	// point.

	// However, virtual-variables can also be used to condense alias sets.
	// Chow96, Fig 5, shows that you can represent multiple indirect variables
	// with a single virtual variable. In fact, we can use a single virtual
	// variable for every indirect variable in the program. But I dont think we
	// will.


	//	PHP has a different and "new" problem: 'normal' syntactic constructs can
	//	have aliasing behaviour, based on the run-time is_ref field of the
	//	value. So some constructs may or may not have aliases:
	//		$p
	//	and some may become 'super-aliases':
	//		$a[$i]
	//		$$a
	//		$p->next
	//		$p->$f
	//
	//	The 'super-aliases' can have is_ref set in their zval, which means they
	//	can can alias a whole rake of other variables. For example:
	//		$$x = 10;
	//		Assume that $x is either "a" or "b", so it can alias either $a or $b.
	//		However, if $a or $b are is_ref, then the assignment to them is even
	//		more indirect.
	//
	//	Super-aliases are tough: conservatively, they could mean that each
	//	variable needs a virtual-variable (we can still use virtual variables,
	//	since assignments to them maintain the 'one-version-one-value'
	//	property).  We would need to perform analysis or this insanity would
	//	spill into 'normal variables'.
	//
	//	We can't really name the set after its real or virtual variable though.
	//	It could be a def of $a or $b, not just $p. So the alias set is {$p, $a,
	//	$b), and you cant just have a variable like v^p to represent it.
	//
	
	

	// So, returning to the HSSA algorithm:
	//		- How do we name the virtual variables?
	//			In C, there is the structure of the addressing expression. We can
	//			use this in PHP too. We dont use the versions of the variables
	//			though.
	//
	//		- So what gets a virtual variable?
	//			Any expression which is not a 'real' variable, but can have a
	//			value (aka abstract locations)
	//					- $a[$i]
	//					- $$a
	//					- $p->next
	//					- $p->$f
	//
	//		- What about super-aliasing?
	//			I dont know. We'll see where it goes. Hopefully nothing (doubt
	//			it).



	// We need different Def-use-webs at different times:
	// Before SSA:
	//		- Chis/Mus must be added.
	//		- Need list of uses/defs for renaming
	//	During SSA:
	//		- newly created phi nodes must be considered
	//	During analysis:
	//		- Analyses can safely update BBs without updating the DUW, as after
	//		the analysis the SSA form will be dropped, and everything will be
	//		recerated for the next analysis.
	//		- DCE needs to remove properties and statements.
	//		- DCE needs to be run after SSA creation to reduce the amount of CHIs.
	
	// So first create DUW with aliasing.
	// During SSA, update DUW with phi nodes.
	// After SSA, recreate the DUW, using an empty alias set, as the alias
	// results will be explicit in the MU/CHIs.

	// 1) Assign virtual variables to indirect variables in the program

	// Do it on the fly

	//	2)	Perform alias analysis and insert MU and CHI for all scalar and
	//		virtual variables.


	
	// The alias sets are passed to def-use-web, which adds MUs and CHIs
	// appropriately.

	//	3) Insert PHIs using Cytron algorithm, including CHI as assignments

	// We use Cooper/Torczon, Section 9.3.3, with some minor changes. Since we
	// dont have a list of global names, we iterate through all blocks, rather
	// than the blocks corresponding to the variable names. 

	// For an assignment to X in BB, add a PHI function for variable X in the
	// dominance frontier of BB.

	// 4) Rename all scalar and virtual variables using Cytron algorithm
	
	// TODO: Zero versioning is actually useful, so add steps 5 and 6. There
	// is not necessarily a need to combine zero versioning with GVN, but we
	// may want GVN later.
	
	// HSSA renames variables using CHIs. Although it might be possible to do
	// something with a CHI when coming out of HSSA form (say, adding copies
	// maybe), HSSA just says to drop the CHIs. But then, you need to drop the
	// indices of all variables, or there will be no link between the RHS of a
	// CHI and its LHS when used later. This adds an invariant to the HSSA
	// form that variables with the same name, but different subscripts,
	// cannot have overlapping live ranges (Cooper/Torczon gives an example
	// where this would break).

	// In terms of phc, this is a boon. It means we dont have to work out a
	// fancy register-allocation solution to avoid massive speed losses due to
	// copy-on-write problems.

	// GVN and PRE both can potentially introduce overlapping live-ranges, but
	// HSSA has versions of both of these. I haven't looked at them, but they
	// must support the overlapping-live-ranges invariant.

From convert_out_of_hssa_form () in HSSA.cpp:

	// There are two problems when coming out of SSA form:
	//		1.) variable-variables: i_0 is not the same as i
	//		2.) CHI nodes update variable indices, but when you drop the chi
	//		nodes, you lose the relationship between them. Renumbering is
	//		possible, I suppose, but not as good as:
	//
	//	The solution is to drop the indices when coming out of SSA form.
	//	(Warning, this could hide bugs unfortunately). The only real problem
	//	is to make sure that variables with overlapping live ranges are not
	//	created. This could happen in copy-propagation, value numbering, or
	//	PRE. I suspect the latter two can be avoided by using the HSSA
	//	algorithms. For copy-propagation, I'll just have to be careful.

	// We avoid the critical edge problem because we have only 1 statement per
	// block. We do not add blocks for phi nodes, because we do not overwrite
	// phi nodes with Rvalues.

From top of Def_use_web.cpp:

/*
 * SSA-web. 
 *
 * Use the SSA-web (which doesnt actually rely on SSA form, nor is
 * it built during it) both for getting into SSA form, and for creating the
 * SSA web.
 */

After build-web in Def_use_web.cpp:

// TODO: CHIs are not created for the parameters to a method call. They
// clearly should be.

// TODO:
// There is a special problem that occurs when you have two indirect
// assignments in the same statement. Suppose you have:
//
//		$x = my_func ($y);
//
//	Then you have to add CHIs for the aliases of $y AND for the aliases of
//	$x. However, the CHIs for the variables which alias $x do not occur at
//	the same time as the variables which alias $y. Instead, $y's aliases
//	should occur after the method invocation, and $x's aliases should occur
//	after the assignment to $x. $x is in the first set, but not in the
//	second. Anything which aliases both $y and $x gets 2 CHIs. $y will get
//	2 CHIs.
//
//	So:
//		$x0 = 5;
//		$x2 = my_func ($y0);
//		$x1 = CHI ($x0); // METHOD
//		$y1 = CHI ($y0); // METHOD
//		$y2 = CHI ($y1); // ASSIGNMENT
//
//	Some interesting notes:
//		- There is no use of $x1.
//		- This problem only occurs when there can be > 1 assignment, which
//		can only occur in assignments from method invocations.
//		- The same variable can get given a CHI from each of a method's
//		parameters, but that is only 1 CHI overall.
//		- There can only be 1 or 2 CHIs, not more (see above).
//		- If we were to use zero versions, the first chi would have a zero
//		version, since it has no real use.
//		- This is only really important for getting the numbering right.
//		Anywhere that uses phis would get them all.
//
//
//
// Some possible solutions:
//		Associate CHIs with other definitions, maybe each def has a list of
//		maydefs. But there is no def in the function call to associate it
//		with, though I think one could safely be added (the MU would ensure
//		that it is not overwritten).
//
//		Allow multiple CHIs in the CHI list. If there is more than 1 of the
//		same name, they are assumed to be in the same order in which they
//		occur. I believe that the only variable which will only occur once
//		in the variable on the RHS.
//		 - but what about when we have small alias sets? Then we dont really
//		 know which is which.
//		 - besides, keeping track of that seems very buggy
//
// XXX: I like this one best, I think.
//		Have two CHI lists, one for 'mid' statement, one for
//		'post-statement'. Aliases of assignments go in the latter. Aliases
//		due to the call go in the former.
//
//	I think this will also solve the problem of 'vanishing globals'. In the
//	case of:
//		global $x;
//		$x = 5;
//
//	The global statement is remove because $x_0 is not used. However, $x = 5
//	is a must_def of $x_0. We can model it as a may-def however, giving it a
//	CHI in the mid-part, and the CHI in the post-statement part gives it the
//	new value.
//
//	The global statement will not in fact be solved by this. If there were
//	an extra statement, $x = 8 after $x = 5, then $x = 5 would be kept live
//	by this 'Early CHI'.
//
//	How about each assignment to an alias gets a MU of the variables in the
//	statement which created the alias.