docs/imcc/operation.pod

   1 # Copyright (C) 2001-2005, Parrot Foundation.
   2 # $Id$
   3
   4 =head1 NAME
   5
   6 IMCC - operation
   7
   8 =head1 VERSION
   9
  10 =over 4
  11
  12 =item 0.1 initial
  13
  14 =item 0.2 uninitialized warning; optimizations
  15
  16 =item 0.3 merged parsing.pod into this file.
  17
  18 =back
  19
  20 =head1 OVERVIEW
  21
  22 This document describes the principles of IMCC operation.
  23
  24 =head1 DESCRIPTION
  25
  26 The main features of imcc are:
  27
  28 =over 4
  29
  30 =item Source file parsing
  31
  32 =item Register allocation
  33
  34 =item Optimization
  35
  36 =item Code generation
  37
  38 =item Running the code
  39
  40 =back
  41
  42 =head1 SOURCE FILE PARSING
  43
  44 =head2 Overview
  45
  46 IMCC parses and generates code in terms of I<compilation units>. These
  47 are self-contained blocks of code very similar to subroutines.
  48
  49 Code for a compilation unit is created as soon (or not earlier) as the
  50 end of the unit is reached.
  51
  52 {{ Is this true? one sub calling another not-yet compiled sub would
  53    not work in that case. }}
  54
  55
  56 =head2 Symbols, constants and labels
  57
  58 I<Compilation units> maintain their own symbol table containing local
  59 labels and variable symbols. This symbol table, C<hash>, is not visible
  60 to code in different units.
  61
  62 If you need global variables, please use the B<get_{hll,root}_global> opcodes.
  63
  64 Global labels and constants are kept in the global symbol table
  65 C<ghash>. This allows for global constant folding beyond the scope
  66 of individual subroutines.
  67
  68 This also means that you currently can't use the same global symbol (e.g.
  69 subroutine name) in different namespaces. The following creates invalid code:
  70
  71 =begin PIR
  72
  73   .sub main
  74      #...
  75   .end
  76
  77    .namespace ["main"]
  78   .sub main
  79      #...
  80   .end
  81
  82 =end PIR
  83
  84 Local labels in different I<compilation units> with the same name are
  85 allowed, though assembling the generated PASM doesn't work. However,
  86 running this code inside imcc is ok. This will probably change in the
  87 future so that local labels are mangled to be unique.
  88
  89
  90
  91 =head1 REGISTER ALLOCATION
  92
  93 Register allocation is done per I<compilation unit>.
  94
  95 IMCC I<identifiers> and I<temporary variables> e.g. $I0 are assigned a
  96 physical parrot register depending on the life range of these
  97 variables. If the life range of one variable doesn't overlap the range
  98 of another variable, they might get the same parrot register. For
  99 instance:
 100
 101 =begin PIR_FRAGMENT
 102
 103    $I0 = 10
 104    $I1 = 20
 105
 106 =end PIR_FRAGMENT
 107
 108 will translate to
 109
 110 =begin PASM
 111
 112    set I0, 10
 113    set I0, 20
 114
 115 =end PASM
 116
 117 provided that $I0 is not used after these lines. In this case, the
 118 assignment to $I0 is redundant and will be optimized away if IMCC is
 119 run with optimization level B<-O2>.
 120
 121 I<PASM registers> keep their register. During the usage of a I<PASM
 122 register> this register will be not get assigned to. Therefore, they
 123 should be used only when absolutely necessary, and you should try to
 124 avoid using them within long pieces of code.
 125
 126 =head2 Basic blocks
 127
 128 To determine the life range of variables, the code gets separated into
 129 pieces, called B<basic block>s. A B<basic block> starts at a label,
 130 which can get jumped to, and ends at a branch instruction.
 131
 132 =head2 Call graph
 133
 134 All connections between the B<basic block>s are calculated. This allows
 135 for:
 136
 137 =head2 Loop detection
 138
 139 where the range and depth of loops is calculated.
 140
 141 =head2 Life analysis
 142
 143 Whenever an operand is marked as an B<OUT> argument, this
 144 operand starts with a new value. This means that at this point the
 145 life range of the symbol ends and a new life range is started, which
 146 allows the allocation of a different register to the same variable or
 147 the same register to a different variable.
 148
 149 Variables used as B<IN> parameters must keep their parrot register
 150 over their usage range.
 151
 152 When C<imcc> detects a register usage, where the first operation is
 153 using (reading) a register (and warnings are enabled), C<imcc> emits
 154 an appropriate message.
 155
 156 Consider these two code snippets (block numbers are attached):
 157
 158 =begin PIR
 159
 160   .sub main :main
 161       $I0 = 0        # 0 initialized
 162       if $I0 goto l1 # 0
 163       $I1 = 1        # 1 init
 164       goto l2        # 1
 165   l1:                # 2
 166       $I1 = 2        # 2 init
 167   l2:                # 3
 168       print $I0      # 3
 169       print $I1      # 3 all paths leading here do init
 170       print "\n"     # 3
 171   .end
 172
 173 =end PIR
 174
 175 and:
 176
 177 =begin PIR
 178
 179   .sub main :main
 180       $I0 = 0         # 0 initialized
 181       if $I0 goto l1  # 0 branch to bb 1 or 2
 182       $I1 = 1         # 1 init only in block 1
 183   l1:                 # 2
 184       print $I0       # 2
 185       print $I1       # 2 no init in code path from block 0
 186       print "\n"      # 2
 187   .end
 188
 189 =end PIR
 190
 191 The latter of these emits the warning:
 192
 193   warning:imcc:propagate_need: '$I1' might be used \
 194   uninitialized in _main:7
 195
 196 =head2 Interference graph
 197
 198 Once the above information is calculated, the next step is to look at
 199 which variables interfere with which others. Non-interfering variables
 200 can be given the same parrot register.
 201
 202 =head2 Register allocation
 203
 204 C<imcc> then starts allocating registers according to a variable's
 205 score. Variables deeply nested inside loops have the highest score and
 206 get a parrot register first. Variables with a long life range (i.e.
 207 with many interferences) get allocated last.
 208
 209 =head1 Optimization
 210
 211 Optimizations are only done when enabled with the B<-O> switch. Please
 212 consult F<t/imcpasm/*.t> for examples. They occur between various
 213 stages and may be repeatedly done: e.g. after converting a conditional
 214 branch to an absolute one, unreachable code will be removed then,
 215 which might cause unused labels ...
 216
 217 =head1 OPTIMIZATIONS WITH -O1
 218
 219 =head2 Constant substitution
 220
 221 Constant arguments to many ops are evaluated. Conditional branches
 222 with constant conditions are converted to unconditional branches.
 223 Integer arguments to float operations are converted to float operands.
 224
 225 =head2 If-branch optimization
 226
 227 A sequence of code:
 228
 229 =begin PIR_FRAGMENT
 230
 231     .local pmc cond
 232     # ...
 233     if cond, L1
 234     branch L2
 235  L1:
 236     # ...
 237  L2:
 238
 239 =end PIR_FRAGMENT
 240
 241 will be converted to
 242
 243 =begin PIR_FRAGMENT
 244
 245     .local pmc cond
 246     # ...
 247     unless cond, L2
 248     # ...
 249  L2:
 250
 251 =end PIR_FRAGMENT
 252
 253 The same is done for other conditional branches B<gt>, B<ge>, B<eq>
 254 and their reverse meanings.
 255
 256 =head2 Branches to branches
 257
 258 Unconditional branch sequences get optimized to jumps to the final label.
 259
 260 =head2 Unused labels
 261
 262 Unreferenced labels are deleted.
 263
 264 =head2 Dead code removal
 265
 266 Code not reachable after an unconditional branch instruction and basic
 267 blocks that are not entered from somewhere get removed.
 268
 269 =head1 OPTIMIZATIONS WITH -O2
 270
 271 Note: These are currently experimental and might not do the Right
 272 Thing.
 273
 274 =head2 Used LHS once
 275
 276 For a sequence of code
 277
 278 =begin PIR_FRAGMENT
 279
 280    $I0 = 10
 281    $I1 = 20
 282
 283 =end PIR_FRAGMENT
 284
 285 where B<$I0> is not used again, the first assignment will be tossed,
 286 resulting in code like:
 287
 288 =begin PASM
 289
 290    set I0, 20
 291
 292 =end PASM
 293
 294 =head2 Loop optimization
 295
 296 Instructions which are invariant to a loop are pulled out of the loop
 297 and inserted in front of the loop entry.
 298
 299 =head1 Code generation
 300
 301 C<imcc> either generates PASM or else directly generates a PBC file for
 302 running with parrot.
 303
 304 =head1 Running code
 305
 306 Additionally the generated code can be run immediately inside imcc.
 307 All parrot runtime options like B<-R jit> or B<-t> are available.
 308
 309 =head1 FILES
 310
 311 F<imc.c>, F<cfg.c>, F<optimizer.c>, F<pbc.c>
 312
 313 =head1 AUTHOR
 314
 315 Leopold Toetsch <lt@toetsch.at>
 316