[LLVMdev] What if there is no Legalized pass?

[Andrew Lenharth]

On Wed, 2005-05-11 at 17:48 +0800, Tzu-Chien Chiu wrote:
> I cannot understand what does the paragraph mean. Could anyone please
> elaborate it?
> 
> http://llvm.cs.uiuc.edu/ChrisLLVM/docs/CodeGenerator.html#selectiondag_legalize
> 
> "Instead of using a Legalize pass, we could require that every
> target-specific selector supports and expands every operator and type
> even if they are not supported and may require many instructions to
> implement (in fact, this is the approach taken by the "simple"
> selectors). However, using a Legalize pass allows all of the
> cannonicalization patterns to be shared across targets which makes it
> very easy to optimize the cannonicalized code because it is still in
> the form of a DAG."
> 
> * what is "the cannonicalization pattern"? sum of product?

Say the expantion of 64bit adds on an architecture that only has 32 bit
registers.  The zero and sign extending of smaller values to fit in
registers.  The putting of the constant as the second operand to
additions.  Stuff like that.

Generally, handle all variable size issues, handle architectures that
lack certain instructions, handle instructions that are only available
for certain registrer types.

> * "makes it very easy to optimize the cannonicalized code"? does it
> refer to "the pre-legalize optimization" ?

So there are really 2 optimizations going on as/after the legalize
happens.  First, as the DAG is being constructed and legalized,
optimizations happen.  Redundent zero extends are eliminated,
unnecessarily long bitmasks are shortened, constants are folded, suff
like that.

Then the code generators have a DAG which they patten match on.  So they
may match several DAG nodes to a single instruction:

       y \
-1 -> XOR -> AND  == Alpha::BIC x y
x /

Add x,y -> ZeroExtend(32) == Alpha::ADDL

(or see all the branchCC and selectCC matching in AlphaISelPattern.cpp)

Hope that helps

Andrew