# LLVM Instruction Scheduling
###### tags: `llvm`
## Framework architecture
### DAG
SD Scheduler
- use Selection DAG

MI Scheduler
- use Scheduling DAG

### Algorithm
List Scheduling-
1. Dependency tree
- resources hazard - reg, unit... etc.
2. Edge weight
- different register depence will cause diffenet latency
- each instruction has its own latency
- ...
3. Strategy
- pick the node has maximum latency
- depend on target design
- VLIW
- ILP
- out-of-order
- ...etc

### Post RA Hazard Recognizer
check the hazard in the final pass of the pre-Emited step, before AsmPrinter
- what's it to do?
- Data Hazard
- insert Nops while hazard happened
- if the processor will stall automatically, do nothing
- Control Hazard
- insert Nops
- most processor cant handle control hazard by itself
#### How
1. put machine instruct into vector
2. check the hazard befor the position in the vector
3. return the number of the latency
4. insert the noops
5. loop to `1.

digraph hierarchy {
    nodesep=2.0 // increases the separation between nodes
	                
	node [color=Gary,fontname=Courier,shape=box]
	edge [color=Block]
    
    start [label=start]
    first [label="put machine instruct\ninto vector"]
    sec [label="check hazard"]
    thr [label="get the number of\nthe hazard's latency"]
    fiv [label="insert the noops"]
    if [label="have MI",shape=diamond];
    end [label=end]
    
    start->if;
    first->sec;
    sec->thr;
    thr->fiv;
    fiv->if;
    if->first[lable = "yes"]
    if->end[label = "no"]
}