|
Perl 5 Wiki
Optree guts
Various material about the internal Perl compilation representation during parsing and optimization, before the actual execution begins. The "B" optree.
Maybe the summary should go to some new perloptreeguts document. Brief SummaryThe brief summary is very well described in the Compiled-code of perlguts.
When Perl parses the source code (via Yacc perly.y), the so-called optree, a tree of basic perl OP structs pointing to simple pp_ functions, is generated bottom-up. OPs are created by the newFOO() functions, which are called from the parser (in perly.y) as the code is parsed. For example the Perl code $a + $b * $c would cause the equivalent of the following to be called (oversimplifying a bit):
newBINOP(OP_ADD, flags,
newSVREF($a),
newBINOP(OP_MULTIPLY, flags, newSVREF($b), newSVREF($c))
)
The simplest type of op structure is OP: this has no children. Unary operators, UNOP s, have one child, and this is pointed to by the op_first field. Binary operators (BINOP s) have not only an op_first field but also an op_last field. The most complex type of op is a LISTOP, which has any number of children. In this case, the first child is pointed to by op_first and the last child by op_last. The children in between can be found by iteratively following the op_sibling pointer from the first child to the last. There are also two other op types: a PMOP holds a regular expression, and has no children, and a LOOP may or may not have children. If the op_sibling field is non-zero, it behaves like a LISTOP . To complicate matters, if a UNOP is actually a null op after optimization (see " Compile pass 2: context propagation") it will still have children in accordance with its former type. The beautiful thing about the optree representation is that it is a strict 1:1 mapping to the actual source code, which is proven by the B::Deparse module, which generates readable source for the current optree. Well, almost. The CompilerPerl's compiler is essentially a 3-pass compiler with interleaved phases:
Compile pass 1: check routines and constant foldingThe bottom-up pass is represented by all the "newOP" routines and the ck_ routines. The bottom-upness is actually driven by yacc. So at the point that a ck_ routine fires, we have no idea what the context is, either upward in the syntax tree, or either forward or backward in the execution order. (The bottom-up parser builds that part of the execution order it knows about, but if you follow the "next" links around, you'll find it's actually a closed loop through the top level node. When creating the ops in the first step, still bottom-up, for each op a check function (ck_) is called, which theroretically may destructively modify the whole tree, but mostly it just nullifies the current op. Or it might set the op_next pointer. See " Check Functions" for more. Also, the constant folding routine fold_constants() may nullify certain ops, which are skipped during final execution. See " Constant Folding" for more. Compile pass 2: context propagation
The context determines the type of the return value. Whenever the bottom-up parser gets to a node that supplies context to its components, it invokes that portion of the top-down pass that applies to that part of the subtree (and marks the top node as processed, so if a node further up supplies context, it doesn't have to take the plunge again). As a particular subcase of this, as the new node is built, it takes all the closed execution loops of its subcomponents and links them into a new closed loop for the higher level node. But it's still not the real execution order. Todo: sample where this op flag is stored Additional context-dependent optimizations are performed at this time. Since at this moment the compile tree contains back-references (via "thread" pointers), nodes cannot be free()d now. To allow optimized-away nodes at this stage, such nodes are null()ified instead of free()ing (i.e. their type is changed to OP_NULL). Compile pass 3: peephole optimizationThe actual execution order is not known till we get a grammar reduction to a top-level unit like a subroutine or file that will be called by "name" rather than via a "next" pointer. At that point, we can call into peep() to do that code's portion of the 3rd pass. It has to be recursive, but it is recursive on basic blocks (See B::Bblock), not on tree nodes.
So finally, when the full parse tree is generated, the peephole optimizer peep() is running. Note that since the last walk the early sibling pointers for recursive (bottom-up) meta-inspection are not needed anymore. The final exec order is guaranteed by the op_next field as you can see in the runops. (See " Walkers or runops" at the end.) basic vs exec order
The highly recursive Yacc parser generates the initial optree in so-called "basic" order. This is how the optree is stored internally. To save memory and run-time the final execution order of the ops in sequential order is not copied around, just the next pointers are rehooked to the so-called "exec" order. Walkers can run in "basic" or "exec" order. OP Structure and Inheritance
The basic struct op looks basically like Each op is defined in size, arguments, return values, class and more in the opcode.pl table. (See " OP Class Declarations in opcode.pl below.) The class of an OP determines its size and the number of children. But the number and type of arguments is not so easy to declare as in C. opcode.pl tries to declare some XS-prototype like arguments, but in lisp we would say most ops are "special", context-dependent, hard to parse. B.pm which represents the ops as perl objects contains these classes and inheritance: @B::OP::ISA = 'B::OBJECT'; @B::UNOP::ISA = 'B::OP'; @B::BINOP::ISA = 'B::UNOP'; @B::LOGOP::ISA = 'B::UNOP'; @B::LISTOP::ISA = 'B::BINOP'; @B::SVOP::ISA = 'B::OP'; @B::PADOP::ISA = 'B::OP'; @B::PVOP::ISA = 'B::OP'; @B::LOOP::ISA = 'B::LISTOP'; @B::PMOP::ISA = 'B::LISTOP'; @B::COP::ISA = 'B::OP'; @B::SPECIAL::ISA = 'B::OBJECT'; @B::optype = qw(OP UNOP BINOP LOGOP LISTOP PMOP SVOP PADOP PVOP LOOP COP); op.h contains the gory details. Let's check it out. OP Class Declarations in opcode.pl
The full list of op declarations is defined as DATA in opcode.pl. The class signifiers in opcode.pl are:
Other options within opcode.pl are:
Values for the operand types are;
BASEOP
All op classes have a single character signifier for easier definition in opcode.pl.
Below are the BASEOP fields, which reflect B::OP, for Perl 5.10. op_nextPointer to next ppcode to execute after this one. Top level pre-grafted op points to first op, but this is replaced when op is grafted in, when this op will point to the real next op, and the new parent takes over role of remembering starting op. Now, who wrote this prose? Anyway, that is why it is called guts. op_siblingThe first child is op_first, the last is op_last, and the children in between are interconnected by op_sibling. This is at run-time only used for LISTOPs. So why is it in the BASEOP struct carried around for every op? And why at the second place and not as third? Because of the complicated Yacc parsing and later optimization order as explained in Compile pass 1: check routines and constant folding the op_next pointers are not enough, so op_sibling's are required. The final and fast execution order by just following the op_next chain is expensive to calculate. op_ppaddrPointer to current ppcode's function. The so called "opcode". op_madpropPointer to the op's MADPROP struct. Only with -DMAD. Since 5.10. See " MAD" below. op_targPADOFFSET to "unnamed" op targets/GVs/constants, wasting no SV. op_typeThe type of the operation. Since 5.10 we have the next five fields added, which replaced U16 op_seq op_optWhether or not the op has been optimised by the peephole optimiser. See the comments in S_clear_yystack() in perly.c for more details on the following three free flags. They are just for freeing temporary ops on the stack.
But we might have statically allocated op in the data segment, esp. with the perl compiler's B::C module. Then we are not allowed to free those static ops. Note: Trying to free a static struct is considered harmful. op_latefreeTell op_free() to clear this op (and free any kids) but not yet deallocate the struct. This means that the op may be safely op_free()d multiple times. On static ops you just set this to 1 and after the first op_free, to free the attached PV's, HEK's and so on, the op_latefreed is automatically set and further op_free called are just ignored. op_latefreedMark that a op_latefree op has already been op_free()d. So this is the real blocker within op_free. op_attachedThis op (sub)tree has been attached to the CV PL_compcv, and therefore doesn't need to be refcount--. op_spareThree spare bits in this bitfield above. At least they survived 5.10. Those last two fields have been in all perls: op_flags
Flags common to all operations. op_privateFlags peculiar to a particular operation (BUT, by default, set to the number of children until the operation is privatized by a check routine, which may or may not check number of children). This flag is normally used to hold op specific context hints, such as HINT_INTEGER. This flag is directly attached to each relevant op in the subtree of the context. Note that there's no general context or class pointer for each op, as in a functional language. So we are limited to max 32 lexical pragma hints or less. See " Lexical Pragmas". The exact op.h BASEOP history for the parts after op_type and before op_flags is: <=5.8: U16 op_seq; 5.9.4: unsigned op_opt:1; unsigned op_static:1; unsigned op_spare:5; >=5.10: unsigned op_opt:1; unsigned op_latefree:1; unsigned op_latefreed:1; unsigned op_attached:1; unsigned op_spare:3; The full list of all BASEOP's is: $ perl -ane 'print if $F[3] =~ /0$/' opcode.pl stub stub ck_null 0 pushmark pushmark ck_null s0 wantarray wantarray ck_null is0 break break ck_null 0 continue continue ck_null 0 fork fork ck_null ist0 wait wait ck_null isT0 getppid getppid ck_null isT0 time time ck_null isT0 tms times ck_null 0 ghostent gethostent ck_null 0 gnetent getnetent ck_null 0 gprotoent getprotoent ck_null 0 gservent getservent ck_null 0 ehostent endhostent ck_null is0 enetent endnetent ck_null is0 eprotoent endprotoent ck_null is0 eservent endservent ck_null is0 gpwent getpwent ck_null 0 spwent setpwent ck_null is0 epwent endpwent ck_null is0 ggrent getgrent ck_null 0 sgrent setgrent ck_null is0 egrent endgrent ck_null is0 getlogin getlogin ck_null st0
You might note, that none has a fixed number or arguments. Nothing behind the "0", for BASEOP. UNOPThe unary op class signifier is 1, for one child, pointed to by op_first.
struct unop {
BASEOP
OP * op_first;
}
$ perl -F"/\cI+/" -ane 'print if $F[3] =~ /1$/' opcode.pl rv2gv ref-to-glob cast ck_rvconst ds1 rv2sv scalar dereference ck_rvconst ds1 av2arylen array length ck_null is1 rv2cv subroutine dereference ck_rvconst d1 refgen reference constructor ck_spair m1 L srefgen single ref constructor ck_null fs1 S regcmaybe regexp internal guard ck_fun s1 S regcreset regexp internal reset ck_fun s1 S preinc preincrement (++) ck_lfun dIs1 S i_preinc integer preincrement (++) ck_lfun dis1 S predec predecrement (--) ck_lfun dIs1 S i_predec integer predecrement (--) ck_lfun dis1 S postinc postincrement (++) ck_lfun dIst1 S i_postinc integer postincrement (++) ck_lfun disT1 S postdec postdecrement (--) ck_lfun dIst1 S i_postdec integer postdecrement (--) ck_lfun disT1 S negate negation (-) ck_null Ifst1 S i_negate integer negation (-) ck_null ifsT1 S not not ck_null ifs1 S complement 1's complement (~) ck_bitop fst1 S rv2av array dereference ck_rvconst dt1 rv2hv hash dereference ck_rvconst dt1 flip range (or flip) ck_null 1 S S flop range (or flop) ck_null 1 method method lookup ck_method d1 entersub subroutine entry ck_subr dmt1 L leavesub subroutine exit ck_null 1 leavesublv lvalue subroutine return ck_null 1 leavegiven leave given block ck_null 1 leavewhen leave when block ck_null 1 leavewrite write exit ck_null 1 dofile do "file" ck_fun d1 S leaveeval eval "string" exit ck_null 1 S #evalonce eval constant string ck_null d1 S Here we have some ops with args. Of course, UNOPs. BINOPThe BINOP class signifier is 2, for two children, pointed to by op_first and op_last.
struct binop {
BASEOP
OP * op_first;
OP * op_last;
}
$ perl -F"/\cI+/" -ane 'print if $F[3] =~ /2$/' opcode.pl gelem glob elem ck_null d2 S S aassign list assignment ck_null t2 L L pow exponentiation (**) ck_null fsT2 S S multiply multiplication (*) ck_null IfsT2 S S i_multiply integer multiplication (*) ck_null ifsT2 S S divide division (/) ck_null IfsT2 S S i_divide integer division (/) ck_null ifsT2 S S modulo modulus (%) ck_null IifsT2 S S i_modulo integer modulus (%) ck_null ifsT2 S S repeat repeat (x) ck_repeat mt2 L S add addition (+) ck_null IfsT2 S S i_add integer addition (+) ck_null ifsT2 S S subtract subtraction (-) ck_null IfsT2 S S i_subtract integer subtraction (-) ck_null ifsT2 S S concat concatenation (.) or string ck_concat fsT2 S S left_shift left bitshift (<<) ck_bitop fsT2 S S right_shift right bitshift (>>) ck_bitop fsT2 S S lt numeric lt (<) ck_null Iifs2 S S i_lt integer lt (<) ck_null ifs2 S S gt numeric gt (>) ck_null Iifs2 S S i_gt integer gt (>) ck_null ifs2 S S le numeric le (<=) ck_null Iifs2 S S i_le integer le (<=) ck_null ifs2 S S ge numeric ge (>=) ck_null Iifs2 S S i_ge integer ge (>=) ck_null ifs2 S S eq numeric eq (==) ck_null Iifs2 S S i_eq integer eq (==) ck_null ifs2 S S ne numeric ne (!=) ck_null Iifs2 S S i_ne integer ne (!=) ck_null ifs2 S S ncmp numeric comparison (<=>)ck_null Iifst2 S S i_ncmp integer comparison (<=>)ck_null ifst2 S S slt string lt ck_null ifs2 S S sgt string gt ck_null ifs2 S S sle string le ck_null ifs2 S S sge string ge ck_null ifs2 S S seq string eq ck_null ifs2 S S sne string ne ck_null ifs2 S S scmp string comparison (cmp) ck_null ifst2 S S bit_and bitwise and (&) ck_bitop fst2 S S bit_xor bitwise xor (^) ck_bitop fst2 S S bit_or bitwise or (|) ck_bitop fst2 S S smartmatch smart match ck_smartmatch s2 aelem array element ck_null s2 A S helem hash element ck_null s2 H S lslice list slice ck_null 2 H L L xor logical xor ck_null fs2 S S leaveloop loop exit ck_null 2 LOGOPThe LOGOP class signifier is |.
A LOGOP has the same structure as a BINOP. Two children, just the second field has another name op_other instead of op_last.
struct logop {
BASEOP
OP * op_first;
OP * op_other;
};
$ perl -F"/\cI+/" -ane 'print if $F[3] =~ /\|$/' opcode.pl
regcomp regexp compilation ck_null s| S
substcont substitution iterator ck_null dis|
grepwhile grep iterator ck_null dt|
mapwhile map iterator ck_null dt|
range flipflop ck_null | S S
and logical and (&&) ck_null |
or logical or (||) ck_null |
dor defined or (//) ck_null |
cond_expr conditional expr ck_null d|
andassign log. and assign. (&&=) ck_null s|
orassign log. or assign. (||=) ck_null s|
dorassign defined or assign. (//=) ck_null s|
entergiven given() ck_null d|
enterwhen when() ck_null d|
entertry eval {block} ck_null |
once once ck_null |
LISTOPThe LISTOP class signifier is @.
struct listop {
BASEOP
OP * op_first;
OP * op_last;
};
This is most complex type, it may have any number of children. The first child is pointed to by op_first and the last child by op_last. The children in between can be found by iteratively following the op_sibling pointer from the first child to the last. At all 99 ops from 366 are LISTOP's. This is the least restrictive format, that's why. $ perl -F"/\cI+/" -ane 'print if $F[3] =~ /\@$/' opcode.pl
bless bless ck_fun s@ S S?
glob glob ck_glob t@ S?
stringify string ck_fun fsT@ S
atan2 atan2 ck_fun fsT@ S S
substr substr ck_substr st@ S S S? S?
vec vec ck_fun ist@ S S S
index index ck_index isT@ S S S?
rindex rindex ck_index isT@ S S S?
sprintf sprintf ck_fun fmst@ S L
formline formline ck_fun ms@ S L
crypt crypt ck_fun fsT@ S S
aslice array slice ck_null m@ A L
hslice hash slice ck_null m@ H L
unpack unpack ck_unpack @ S S?
pack pack ck_fun mst@ S L
split split ck_split t@ S S S
join join or string ck_join mst@ S L
list list ck_null m@ L
anonlist anonymous list ([]) ck_fun ms@ L
anonhash anonymous hash ({}) ck_fun ms@ L
splice splice ck_fun m@ A S? S? L
... and so on, until
syscall syscall ck_fun imst@ S L
PMOP
The PMOP "pattern matching class signifier is `/` for matching.
The internal struct changed completely with 5.10, as the underlying engine. Below is the current struct pmop. You will not like it.
struct pmop {
BASEOP
OP * op_first;
OP * op_last;
#ifdef USE_ITHREADS
IV op_pmoffset;
#else
REGEXP * op_pmregexp; /* compiled expression */
#endif
U32 op_pmflags;
union {
OP * op_pmreplroot; /* For OP_SUBST */
#ifdef USE_ITHREADS
PADOFFSET op_pmtargetoff; /* For OP_PUSHRE */
#else
GV * op_pmtargetgv;
#endif
} op_pmreplrootu;
union {
OP * op_pmreplstart; /* Only used in OP_SUBST */
#ifdef USE_ITHREADS
char * op_pmstashpv; /* Only used in OP_MATCH, with PMf_ONCE set */
#else
HV * op_pmstash;
#endif
} op_pmstashstartu;
};
Before we had no union, but a op_pmnext, which never really worked.
struct pmop {
BASEOP
OP * op_first;
OP * op_last;
U32 op_children;
OP * op_pmreplroot;
OP * op_pmreplstart;
PMOP * op_pmnext; /* list of all scanpats */
REGEXP * op_pmregexp; /* compiled expression */
U16 op_pmflags;
U16 op_pmpermflags;
U8 op_pmdynflags;
}
So op_pmnext, op_pmpermflags and op_pmdynflags are gone. $ perl -F"/\cI+/" -ane 'print if $F[3] =~ /\/$/' opcode.pl pushre push regexp ck_null d/ match pattern match (m//) ck_match d/ qr pattern quote (qr//) ck_match s/ subst substitution (s///) ck_match dis/ S SVOP
The SVOP class is very special, and can even change dynamically. A SVOP holds a SV and is in case of an FILESTATOP the GV for the filehandle argument, and in case of trans (a PVOP) with utf8 a reference to a swash (i.e., an RV pointing to an HV).
struct svop {
BASEOP
SV * op_sv;
};
Most old SVOP's were changed to PADOP's when threading was introduced, to privatize the global SV area to thread-local scratchpads. SVOP_OR_PADOP
The op aelemfast is a PADOP with threading and a simple SVOP without. aelemfast constant array element ck_null s$ A S PVOP_OR_SVOPThe only op here is trans, where the class is dynamically defined, dependent on the utf8 settings in the op_private hints.
case OA_PVOP_OR_SVOP:
return (o->op_private & (OPpTRANS_TO_UTF|OPpTRANS_FROM_UTF))
? OPc_SVOP : OPc_PVOP;
trans transliteration (tr///) ck_null is" S Character translations (tr///) are usually a PVOP, keeping a pointer to a table of shorts used to look up translations. Under utf8 however, a simple table isn't practical; instead, the OP is an SVOP, and the SV is a reference to a swash (i.e., an RV pointing to an HV). PADOPThe PADOP class signifier is $ for temp. scalars.
A new PADOP creates a new temporary scratchpad for threads only. A PADLIST scratchpad is a special context stack, a array-of-array data structure attached to a CV (ie a sub or commonly called a "closure"), to store lexical variables and opcode temporary and per-thread values. See perlguts/Scratchpads. Only my/our variable (SVs_PADMY/SVs_PADOUR) slots get valid names. The rest are op targets/GVs/constants which are statically allocated or resolved at compile time. These don't have names by which they can be looked up from Perl code at run time through eval "" like my/our variables can be. Since they can't be looked up by "name" but only by their index allocated at compile time (which is usually in op_targ), wasting just a name SV for them doesn't make sense.
struct padop {
BASEOP
PADOFFSET op_padix;
};
$ perl -F"/\cI+/" -ane 'print if $F[3] =~ /\$$/' opcode.pl const constant item ck_svconst s$ gvsv scalar variable ck_null ds$ gv glob value ck_null ds$ anoncode anonymous subroutine ck_anoncode $ rcatline append I/O operator ck_null t$ aelemfast constant array element ck_null s$ A S method_named method with known name ck_null d$ hintseval eval hints ck_svconst s$ PVOP
This is a simple unary op, holding a string. The PVOP class signifier is " for strings.
struct pvop {
BASEOP
char * op_pv;
};
$ perl -F"/\cI+/" -ane 'print if $F[3] =~ /\"$/' opcode.pl trans transliteration (tr///) ck_match is" S LOOP
The LOOP class signifier is {.
struct loop {
BASEOP
OP * op_first;
OP * op_last;
OP * op_redoop;
OP * op_nextop;
OP * op_lastop;
};
$ perl -F"/\cI+/" -ane 'print if $F[3] =~ /\{$/' opcode.pl
enteriter foreach loop entry ck_null d{
enterloop loop entry ck_null d{
COP
The struct cop, the "Control OP" changed a bit recently, as the BASEOP.
I would have naively called it Context OP, but not Control OP. So why?
cop.h says: But we need block context, eval context, subroutine context, loop context, and even format context. All these are seperate structs defined in cop.h. So the COPs are not really that important, as the actual Cx context structs are. Just the CopSTASH is, the current package symbol table hash ("stash"). Another famous COP is PL_compiling, which sets the temporary compilation environment.
struct cop {
BASEOP
line_t cop_line; /* line # of this command */
char * cop_label; /* label for this construct */
#ifdef USE_ITHREADS
char * cop_stashpv; /* package line was compiled in */
char * cop_file; /* file name the following line # is from */
#else
HV * cop_stash; /* package line was compiled in */
GV * cop_filegv; /* file the following line # is from */
#endif
U32 cop_hints; /* hints bits from pragmata */
U32 cop_seq; /* parse sequence number */
/* Beware. mg.c and warnings.pl assume the type of this is STRLEN *: */
STRLEN * cop_warnings; /* lexical warnings bitmask */
/* compile time state of %^H. See the comment in op.c for how this is
used to recreate a hash to return from caller. */
struct refcounted_he * cop_hints_hash;
};
The COP class signifier is ; and there are only two such ops. nextstate next statement ck_null s; dbstate debug next statement ck_null s;
_ Hmm, there uses to be three. SETSTATE seems to be optimized away, I cannot find it in the source anymore neither. Requires a patch to remove wrong info from the cop.h header. BASEOP_OR_UNOPBASEOP_OR_UNOP has the class signifier %. As the name says, it may be a BASEOP or UNOP, it may have an optional op_first field.
The list of % ops is quite large, it has 84 ops. $ perl -F"/\cI+/" -ane 'print if $F[3] =~ /%$/' opcode.pl ... quotemeta quotemeta ck_fun fstu% S? aeach each on array ck_each % A akeys keys on array ck_each t% A avalues values on array ck_each t% A each each ck_each % H values values ck_each t% H keys keys ck_each t% H delete delete ck_delete % S exists exists ck_exists is% S pop pop ck_shift s% A? shift shift ck_shift s% A? caller caller ck_fun t% S? reset symbol reset ck_fun is% S? exit exit ck_exit ds% S? ... FILESTATOPA FILESTATOP may be a UNOP, PADOP, BASEOP or SVOP. It has the class signifier - for the first char of the file tests (-e, -r, -w, ...) The file stat OPs are created via UNI(OP_foo) in toke.c but use the OPf_REF flag to distinguish between OP types instead of the usual OPf_SPECIAL flag. As usual, if OPf_KIDS is set, then we return OPc_UNOP so that walkoptree can find our children. If OPf_KIDS is not set then we check OPf_REF. Without OPf_REF set (no argument to the operator) it's an OP; with OPf_REF set it's an SVOP (and op_sv is the GV for the filehandle argument).
case OA_FILESTATOP:
return ((o->op_flags & OPf_KIDS) ? OPc_UNOP :
#ifdef USE_ITHREADS
(o->op_flags & OPf_REF) ? OPc_PADOP : OPc_BASEOP);
#else
(o->op_flags & OPf_REF) ? OPc_SVOP : OPc_BASEOP);
#endif
lstat lstat ck_ftst u- F stat stat ck_ftst u- F ftrread -R ck_ftst isu- F-+ ftrwrite -W ck_ftst isu- F-+ ftrexec -X ck_ftst isu- F-+ fteread -r ck_ftst isu- F-+ ftewrite -w ck_ftst isu- F-+ fteexec -x ck_ftst isu- F-+ ftis -e ck_ftst isu- F- ftsize -s ck_ftst istu- F- ftmtime -M ck_ftst stu- F- ftatime -A ck_ftst stu- F- ftctime -C ck_ftst stu- F- ftrowned -O ck_ftst isu- F- fteowned -o ck_ftst isu- F- ftzero -z ck_ftst isu- F- ftsock -S ck_ftst isu- F- ftchr -c ck_ftst isu- F- ftblk -b ck_ftst isu- F- ftfile -f ck_ftst isu- F- ftdir -d ck_ftst isu- F- ftpipe -p ck_ftst isu- F- ftsuid -u ck_ftst isu- F- ftsgid -g ck_ftst isu- F- ftsvtx -k ck_ftst isu- F- ftlink -l ck_ftst isu- F- fttty -t ck_ftst is- F- fttext -T ck_ftst isu- F- ftbinary -B ck_ftst isu- F- LOOPEXOPA LOOPEXOP is almost a BASEOP_OR_UNOP. It may be a UNOP if stacked or BASEOP if special or PVOP else.
The next, last, redo, dump and goto ops use OPf_SPECIAL to indicate that a label was omitted (in which case it's a BASEOP) or else a term was seen. Todo ... OP Definition ExampleLet's take a simple example for an opcode declaration in opcode.pl: name description check function flags args left_shift left bitshift (<<) ck_bitop fsT2 S S
The op left_shift has a check function ck_bitop (normally most ops have no check function, just ck_null), and the options fsT2.
f tells the compiler in the first pass to call fold_constants() on this op. See "{link: Compile pass 1: check routines and constant folding}" above.
Now let's inspect the simple definition of this op in pp.c.
PP(pp_left_shift)
{
dVAR; dSP; dATARGET; tryAMAGICbin(lshift,opASSIGN);
{
const IV shift = POPi;
if (PL_op->op_private & HINT_INTEGER) {
const IV i = TOPi;
SETi(i << shift);
}
else {
const UV u = TOPu;
SETu(u << shift);
}
RETURN;
}
}
The first arg is pop'ed from the stack, via POPi, as integer. The second arg is left on the stack (TOPi/TOPu), because it is used as the return value. Todo: explain the opASSIGN magic check.
One IV or UV is produced in the 2nd arg on the stack, dependent on HINT_INTEGER, set by the use integer pragma. What is left is the T flag, "target can be a pad". This is a useful optimization technique.
This is checked in the macro dATARGET Check Functions
The ck_ functions are defined in op.c and not in pp.c, because they belong tightly to the ops and newOP definition, and not to the actual pp_ opcode. That's why the actual op.c file is bigger than pp.c, where the real gore for each op begins. The ck_null check function is the most common. $ perl -F"/\cI+/" -ane 'print $F[2],"\n" if $F[2] =~ /ck_null/' opcode.pl|wc -l 128 But we do have a lot of different check functions. $ perl -F"/\cI+/" -ane 'print $F[2],"\n" if $F[2] =~ /ck_/' opcode.pl|sort -u|wc -l 43 When are they called, how do they look like, what do they do. The macro CHECKOP(type,o) which used to call the ck_ function has a little bit of common logic.
#define CHECKOP(type,o) \
((PL_op_mask && PL_op_mask[type]) \
? ( op_free((OP*)o), Perl_croak(aTHX_ "'%s' trapped by operation mask", PL_op_desc[type]), (OP*)0 ) \
: CALL_FPTR(PL_check[type])(aTHX_ (OP*)o))
So when a global PL_op_mask is fitting to the type, the OP is nullified at once. _Todo: op_mask_ Constant FoldingIn theory pretty easy. If all op's arguments are constant and the op is sideffect free ("purely functional"), replace the op with an constant op as result.
We do it like this: We define the f flag in opcodes.pl, which tells the compiler in the first pass to call But take care, the f op must be sideeffect free, otherwise the sideeffects will be optimized away. Bad. Think of print. E.g. the simple newUNOP() call CHECKOP() and then fold_constants() it at the end:
OP *
Perl_newUNOP(pTHX_ I32 type, I32 flags, OP *first)
{
if (!first)
first = newOP(OP_STUB, 0);
if (PL_opargs[type] & OA_MARK)
first = force_list(first);
NewOp(1101, unop, 1, UNOP);
unop->op_type = (OPCODE)type;
unop->op_ppaddr = PL_ppaddr[type];
unop->op_first = first;
unop->op_flags = (U8)(flags | OPf_KIDS);
unop->op_private = (U8)(1 | (flags >> 8));
unop = (UNOP*) CHECKOP(type, unop);
if (unop->op_next)
return (OP*)unop;
return fold_constants((OP *) unop);
We see the check function CHECKOP and if from there no op_next pointer was attached (I told you, check functions can be destructive), we try to fold it. The actual fold_constants() function is pretty hairy and should better not be viewed by a functional programmers eye. I warned you! After some checking, if it is allowed to fold it, it has to fold it. How do you do that? Well, you fake an op eval of the subtree, and check the result, which must be an sv, pad or mortal temp. But I don't see at first-hand where the possible sideeffects are ironed out. Dangerous. Lexical PragmasTo implement user lexical pragmas, there needs to be a way at run time to get the compile time state of %^H for that block. Storing %^H in every block (or even COP) would be very expensive, so a different approach is taken. The (running) state of %^H is serialised into a tree of HE-like structs. Stores into %^H are chained onto the current leaf as a struct refcounted_he * with the key and the value. Deletes from %^H are saved with a value of PL_sv_placeholder. The state of %^H at any point can be turned back into a regular HV by walking back up the tree from that point's leaf, ignoring any key you've already seen (placeholder or not), storing the rest into the HV structure, then removing the placeholders. Hence memory is only used to store the %^H deltas from the enclosing COP, rather than the entire %^H on each COP. To cause actions on %^H to write out the serialisation records, it has magic type 'H'. This magic (itself) does nothing, but its presence causes the values to gain magic type 'h', which has entries for set and clear. Perl_magic_sethint updates PL_compiling.cop_hints_hash with a store record, with deletes written by Perl_magic_clearhint. SAVEHINTS saves the current PL_compiling.cop_hints_hash on the save stack, so that t will be correctly restored when any inner compiling scope is exited. HooksWe list some methods for hooks into these early stages.
1. Special execution blocks BEGIN, CHECK, UNITCHECK, INIT, END Special execution blocks BEGIN, CHECK, UNITCHECK, INIT, ENDPerl keeps special arrays of subroutines that are executed at the beginning and at the end of a running Perl program and its program units. These subroutines correspond to the special code blocks: `BEGIN', `CHECK', `UNITCHECK', `INIT' and `END'. (See basics at perlmod.)
Such arrays belong to Perl's internals that you're not supposed to see. Entries in these arrays get consumed by the interpreter as it enters distinct compilation phases, triggered by statements like `require, `use, `do, `eval, etc. BEGIN, UNITCHECK and INIT are FIFO (first-in, first-out) blocks, while CHECK and END are LIFO (last-in, first-out). Devel::Hook allows adding code the start or end of these blocks. Manip::END even tries to remove certain entries. The BEGIN block
A special array of code at PL_beginav, that is executed before main_start. The CHECK blockThis is the B compiler hook, defined at PL_checkav. The UNITCHECK blockA new block since Perl 5.10 at PL_unitcheckav. It runs right after the CHECK block, to seperate possible B compilation hooks from other checks. The INIT blockAt PL_initav. After compilation, before main(). The END block
At PL_endav, after main() ended. Cleanup custom objects. The array contains an undef for each block that has been encountered. It's not really an undef though, it's a kind of raw coderef that's not wrapped in a scalar ref. This leads to fun error messages like Bizarre copy of CODE in sassign when you try to assign one of these values to another variable. See Manip::END how to manipulate this array. The B and O modules - The perl compiler
Malcom Beattie's B modules hooked into the early optree stages to represent the internal ops as perl objects and then added the perl compiler backends. The three main compiler backends are still Bytecode, C and CC, and these do not work for current perl's (yet). Todo: General hooks: compile, debug, bsave, ... B::BytecodeBytecode is the simpliest of of it. It strictly represents the optree and variables, starting from main_root as compressed bytes and has a companion Byteloader module to recreate the optree state. $ perl -MO=Bytecode,-s,-osource.plc source.pl produces via the B::Assembler module the .plc file. And for a module: $ perl -MO=Bytecode,-s,-m,-osource.pmc source.pm
a .pmc file, which is even recognized by "require".
Some gore? Most insn's require exactly one arg, in fact all ops without the PUT/GET_none methods, and the GET and PUT methods are used to en-/decode the arg to binary bytecode. The names are constructed from the GET/PUT prefix and the argument type, such as U8, U16, U32, svindex, opindex, pvindex, hekindex, ...
The PUT method is used in the B::Bytecode compiler within B::Assembler, The full insn table with version (since 5.10), opcode, name, lvalue, argtype and flags is located as DATA in bytecode.pl. Take the simple example perl -MO=Bytecode,-S -e' print "hi" ' which produces about 137 lines of bytecode. The commented .plc bytecode (-S) looks like :
...
# [leave 5]
newopx 22816 # WANT_VOID,KIDS,PARENS, 22816=size:32,type:178
op_next 0
op_targ 1
op_flags 13
op_private 64
# [print 6]
newopx 26784 # WANT_VOID,KIDS, 26784=size:32,type:209
op_next 5
op_targ 0
op_flags 5
op_private 0
# [const 7]
newopx 668 # WANT_SCALAR, 668=size:28,type:5
op_next 6
op_targ 1
op_flags 2
op_private 0
op_sv 0
# [pushmark 8]
newopx 408 # WANT_SCALAR, 408=size:24,type:3
op_next 7
op_targ 0
op_flags 2
op_private 0
# [nextstate 9]
newopx 22328 # WANT_VOID, 22328=size:56,type:174
op_next 8
op_targ 0
op_flags 1
op_private 0
newpv "main\000"
stpv 10
cop_stashpv 10
newpv "bytecode1.pl\000"
stpv 11
cop_file 11
cop_seq 1762
cop_arybase 0
cop_line 1
cop_warnings 0
cop_io 0
# [enter 12]
newopx 22680 # , 22680=size:24,type:177
op_next 9
op_targ 0
op_flags 0
op_private 0
main_start 12
main_root 5
# [CV]
newsvx 12 #
# [CV]
newsvx 13 # CV undef
# [AV]
newsvx 11 # AV undef
# [AV]
newsvx 10 # AV undef
sv_refcnt 1
xav_flags 1
xmg_stash 0
# [AV]
newsvx 10 # AV undef
# [&PL_sv_undef]
ldspecsvx 1 # &PL_sv_undef
# [PV]
newsvx 134366213 # PV "hi"
sv_refcnt 1
newpv "hi\000"
xpv
# -AV-
ldsv 520
av_extend 3
av_pushx 521
av_pushx 522
sv_refcnt 1
xav_flags 1
xmg_stash 0
...
So we always have a pair of op (newopx) with a fixed size argument (U16). 6 <@> leave[1 ref] vKP/REFC ->(end)
[ leave 5 ]
This creates the leave op on the optree. op_next 0 # so this is the end of the optree
op_flags 13 => # WANT_VOID,KIDS,PARENS Note that the size and type for newopx may change for every perl release, and they do. All other argument types are encoded straightforwarded. Well, strings (pv's) are length prefixed (Pascal-style). Only a few ops have no argument, such as ret, pv_free or xpv.
And then there are some hacks with pvcontents instructions, like pregcomp, which are supposed to take a pvcontents Definition in bytecode.pl: pregcomp PL_op pvcontents x Wrong: asm "pregcomp", "some string" Good: asm "newpv", "some string" asm "pregcomp"
We also see that op_next and other pointers are 'relativized' per op index. For comparison, the full Concise section starts in basic order also at "leave", though "leave" is the last op (6) in exec order. $ perl -MO=-qq,Concise -e ' print "hi" ' 6 <@> leave[1 ref] vKP/REFC ->(end) 1 <0> enter ->2 2 <;> nextstate(main 1 -e:1) v ->3 5 <@> print vK ->6 3 <0> pushmark s ->4 4 <$> const[PV "hi"] s ->5 exec order: $ perl -MO=-qq,Concise,-exec -e 'print "hi"' 1 <0> enter 2 <;> nextstate(main 1 -e:1) v 3 <0> pushmark s 4 <$> const[PV "hi"] s 5 <@> print vK 6 <@> leave[1 ref] vKP/REFC
We also see now that the bytecode ops are dumped in reverse basic order.
The B::Disassembler can read the .plc bytecode and produce readable and re-compilable bytecode assembler. newopx 22816 # size:32, type:178 op_next 0 op_targ 1 op_flags 13 op_private 64 newopx 26784 # size:32, type:209 op_next 5 op_targ 0 op_flags 5 op_private 0 newopx 668 # size:28, type:5 op_next 6 op_targ 1 op_flags 2 op_private 0 op_sv 0 ... The relevant B::Debug output for the first three ops "leave", "enter", "nextstate" in basic order would be: LISTOP (0x70a480) op_ppaddr PL_ppaddr[OP_LEAVE] op_next 0x0 op_sibling 0x0 op_targ 1 op_type 178 op_seq 11698 op_flags 13 op_private 64 op_first 0x7122d0 OP [OP_ENTER] op_last 0x669630 LISTOP [OP_PRINT] op_children 3 OP (0x7122d0) op_ppaddr PL_ppaddr[OP_ENTER] op_next 0x709280 COP [OP_NEXTSTATE] op_sibling 0x709280 COP [OP_NEXTSTATE] op_targ 0 op_type 177 op_seq 11693 op_flags 0 op_private 0 COP (0x709280) op_ppaddr PL_ppaddr[OP_NEXTSTATE] op_next 0x680760 OP [OP_PUSHMARK] op_sibling 0x669630 LISTOP [OP_PRINT] op_targ 0 op_type 174 op_seq 11694 op_flags 1 op_private 0 cop_label "" cop_stashpv "main" cop_file "bytecode1.pl" cop_seq 792 cop_arybase 0 cop_line 1 cop_warnings 0x0 cop_io "" You see, bytecode is a pretty good compression of the relevant optree fields in B::Debug in memory. A little bit more gore: B::C.... And now the real gore: B::CC.... MADLarry Wall was working together with Nicholas Clark on the new MAD compiler backend outside of the B approach, dumping the internal optree representation as XML for external comverters. Not working with the tree of live B objects.
The idea is that all the information needed to recreate the original source is stored in the optree. To do this the tokens for the ops are associated with ops, these madprops are a list of key-value pairs, where the key is a character as listed at the end of op.h, the value normally is a string, but it might also be a op, as in the case of a optimized op ('O'). Special for the whitespace key '_' (whitespace before) and '#' (whitespace after), which indicate the whitespace or comment before/after the previous key-value pair.
Why this awful XML and not the rich tree of perl objects? Environment variablesPERL_XMLDUMP="filename.xml" PERL_MADSKILLS="1" perl bla
perl.c checks for those two environment variables, and switches to mad compilation if PERL_XMLDUMP exists. ExampleThe MAD compiler 5-5 roundtrip tool is the script mad/p55.
mad/p55 output source.pl
mad/p55 -Y output source.pl
The almost-finished perl5-to-perl6 converter by Sage LaTorra for the 2006 Google SoC. Pugs uses the translators at the pugs repo in misc/pX/Common/P5_to_P6_Translation/ASTTranslate.hs
kurila uses MAD to convert Perl 5 source to the kurila dialect. kurilapath=/usr/src/perl/kurila-1.9 bleadpath=/usr/src/perl/blead cd $kurilapath madfrom='perl-5.10' madto='kurila-1.9' \ madconvert="/usr/bin/perl $kurilapath/mad/p5kurila.pl" \ madpath="$bleadpath/mad" \ mad/convert /path/to/source.pm PPI, a Perl 5 source parser not related to the optree at all, could also have been used for that. Walkers or runopsThe standard optree walker or runloop is as simple as this ultrafast Perl_runops_standard() in run.c. It starts with main_start and walks the op_next chain until the end. No need to check other fields, strictly linear through the tree. So in fact the perl parser creates the tree, and the optimizer flats the tree to a simple linear list. The compiler backends, B, can simply concentrate on the list.
int
Perl_runops_standard(pTHX)
{
dVAR;
while ((PL_op = CALL_FPTR(PL_op->op_ppaddr)(aTHX))) {
PERL_ASYNC_CHECK();
}
TAINT_NOT;
return 0;
}
To inspect the optree within a perl program, you can also hook PL_runops (see "Pluggable runops" below) to your own perl walker (see e.g. B::Utils for various useful walkers), but you cannot modify the tree from within the B accessors, only via XS. Or via B::Generate as explained in Simon Cozen's Hacking the Optree for Fun.... Todo: Describe the dumper, the debugging and more extended walkers. Pluggable runopsThe compile tree is executed by one of two existing runops functions, in run.c or in dump.c. Perl_runops_debug is used with DEBUGGING and Perl_runops_standard is used otherwise (See above in "{link: Walkers or runops}"). For fine control over the execution of the compile tree it is possible to provide your own runops function. It's probably best to copy one of the existing runops functions and change it to suit your needs. Then, in the BOOT section of your XS file, add the line: PL_runops = my_runops; This function should be as efficient as possible to keep your programs running as fast as possible. Internal and external modificationsTodo: Describe the exported variables and functions which can be hooked, besides simply adding code to the blocks. .. Modify the optree .. See the short description of the internal optimizer in the "Brief Summary", and the three compiler passes. Internally some Acme modules try to play this game.
Best see B::Utils.
Externally we use the compiler backends with O, XS hooks or the new MAD.
Optrees can be much easier modified than almost unparsable source. Compare the simplicity of B::Bytecode to PPI. ModulesThe most important optree module is B::Concise by Stephen McCamant. B::Utils provides abstract-enough optree grep's and walkers with callbacks from the perl level.
Devel::Hook allows adding perl hooks into Devel::TypeCheck tries to verify possible static typing for expressions and variables, a pretty hard problem for compilers, esp. with such a dynamic and untyped variables as Perl 5. Reini Urban is working on an interactive optree debugger, B::Debugger (very raw yet). Various ArticlesThe best source of information is the source. It is very well documented. Simon Cozens has posted the course material to NetThink's Perl 5 Internals training course. This is the currently best available description on that subject. And then of course "Hacking the Optree for Fun... the next step by Simon Cozens for destructive code modification. Joshua ben Jore wrote a 50 minute presentation on Perl 5 VM guts focusing on the optree for SPUG, the Seattle Perl User's Group. Eric Wilhelm wrote a brief tour through the perl compiler backends for the impatient refactorerer. perl_guts_tour as mp3 or as pdf ConclusionSo this is about 30% of the basic optree information so far. Not speaking about the guts. Simon has more 30%, in the source are more 10% to copy&paste, and in the compilers and run-time information is the rest. I hope with the help of some hackers we'll get it done, so that some people will begin poking around in the B backends. And write the wonderful new/old dump functionality (which actually worked in the early years on Solaris), output PIR (parrot code), emit LLVM or another JIT optimized code or even write assemblers. I have a simple one at home. :) Written 2008 on the perl5 wiki with socialtext and pod in parallel by Reini Urban, CPAN ID rurban, with the help of Aristotle Pagaltzis, Gerard Goossen, <your name here>. |
-
4459 views
-
57 revisions
