1*1f5207b7SJohn Levon /* 2*1f5207b7SJohn Levon * Flow - walk the linearized flowgraph, simplifying it as we 3*1f5207b7SJohn Levon * go along. 4*1f5207b7SJohn Levon * 5*1f5207b7SJohn Levon * Copyright (C) 2004 Linus Torvalds 6*1f5207b7SJohn Levon */ 7*1f5207b7SJohn Levon 8*1f5207b7SJohn Levon #include <string.h> 9*1f5207b7SJohn Levon #include <stdarg.h> 10*1f5207b7SJohn Levon #include <stdlib.h> 11*1f5207b7SJohn Levon #include <stdio.h> 12*1f5207b7SJohn Levon #include <stddef.h> 13*1f5207b7SJohn Levon #include <assert.h> 14*1f5207b7SJohn Levon 15*1f5207b7SJohn Levon #include "parse.h" 16*1f5207b7SJohn Levon #include "expression.h" 17*1f5207b7SJohn Levon #include "linearize.h" 18*1f5207b7SJohn Levon #include "flow.h" 19*1f5207b7SJohn Levon #include "target.h" 20*1f5207b7SJohn Levon 21*1f5207b7SJohn Levon unsigned long bb_generation; 22*1f5207b7SJohn Levon 23*1f5207b7SJohn Levon /* 24*1f5207b7SJohn Levon * Dammit, if we have a phi-node followed by a conditional 25*1f5207b7SJohn Levon * branch on that phi-node, we should damn well be able to 26*1f5207b7SJohn Levon * do something about the source. Maybe. 27*1f5207b7SJohn Levon */ 28*1f5207b7SJohn Levon static int rewrite_branch(struct basic_block *bb, 29*1f5207b7SJohn Levon struct basic_block **ptr, 30*1f5207b7SJohn Levon struct basic_block *old, 31*1f5207b7SJohn Levon struct basic_block *new) 32*1f5207b7SJohn Levon { 33*1f5207b7SJohn Levon if (*ptr != old || new == old || !bb->ep) 34*1f5207b7SJohn Levon return 0; 35*1f5207b7SJohn Levon 36*1f5207b7SJohn Levon /* We might find new if-conversions or non-dominating CSEs */ 37*1f5207b7SJohn Levon /* we may also create new dead cycles */ 38*1f5207b7SJohn Levon repeat_phase |= REPEAT_CSE | REPEAT_CFG_CLEANUP; 39*1f5207b7SJohn Levon *ptr = new; 40*1f5207b7SJohn Levon replace_bb_in_list(&bb->children, old, new, 1); 41*1f5207b7SJohn Levon remove_bb_from_list(&old->parents, bb, 1); 42*1f5207b7SJohn Levon add_bb(&new->parents, bb); 43*1f5207b7SJohn Levon return 1; 44*1f5207b7SJohn Levon } 45*1f5207b7SJohn Levon 46*1f5207b7SJohn Levon /* 47*1f5207b7SJohn Levon * Return the known truth value of a pseudo, or -1 if 48*1f5207b7SJohn Levon * it's not known. 49*1f5207b7SJohn Levon */ 50*1f5207b7SJohn Levon static int pseudo_truth_value(pseudo_t pseudo) 51*1f5207b7SJohn Levon { 52*1f5207b7SJohn Levon switch (pseudo->type) { 53*1f5207b7SJohn Levon case PSEUDO_VAL: 54*1f5207b7SJohn Levon return !!pseudo->value; 55*1f5207b7SJohn Levon 56*1f5207b7SJohn Levon case PSEUDO_REG: { 57*1f5207b7SJohn Levon struct instruction *insn = pseudo->def; 58*1f5207b7SJohn Levon 59*1f5207b7SJohn Levon /* A symbol address is always considered true.. */ 60*1f5207b7SJohn Levon if (insn->opcode == OP_SYMADDR && insn->target == pseudo) 61*1f5207b7SJohn Levon return 1; 62*1f5207b7SJohn Levon } 63*1f5207b7SJohn Levon /* Fall through */ 64*1f5207b7SJohn Levon default: 65*1f5207b7SJohn Levon return -1; 66*1f5207b7SJohn Levon } 67*1f5207b7SJohn Levon } 68*1f5207b7SJohn Levon 69*1f5207b7SJohn Levon /* 70*1f5207b7SJohn Levon * Does a basic block depend on the pseudos that "src" defines? 71*1f5207b7SJohn Levon */ 72*1f5207b7SJohn Levon static int bb_depends_on(struct basic_block *target, struct basic_block *src) 73*1f5207b7SJohn Levon { 74*1f5207b7SJohn Levon pseudo_t pseudo; 75*1f5207b7SJohn Levon 76*1f5207b7SJohn Levon FOR_EACH_PTR(src->defines, pseudo) { 77*1f5207b7SJohn Levon if (pseudo_in_list(target->needs, pseudo)) 78*1f5207b7SJohn Levon return 1; 79*1f5207b7SJohn Levon } END_FOR_EACH_PTR(pseudo); 80*1f5207b7SJohn Levon return 0; 81*1f5207b7SJohn Levon } 82*1f5207b7SJohn Levon 83*1f5207b7SJohn Levon /* 84*1f5207b7SJohn Levon * This really should be handled by bb_depends_on() 85*1f5207b7SJohn Levon * which efficiently check the dependence using the 86*1f5207b7SJohn Levon * defines - needs liveness info. Problem is that 87*1f5207b7SJohn Levon * there is no liveness done on OP_PHI & OP_PHISRC. 88*1f5207b7SJohn Levon * 89*1f5207b7SJohn Levon * This function add the missing dependency checks. 90*1f5207b7SJohn Levon */ 91*1f5207b7SJohn Levon static int bb_depends_on_phi(struct basic_block *target, struct basic_block *src) 92*1f5207b7SJohn Levon { 93*1f5207b7SJohn Levon struct instruction *insn; 94*1f5207b7SJohn Levon FOR_EACH_PTR(src->insns, insn) { 95*1f5207b7SJohn Levon if (!insn->bb) 96*1f5207b7SJohn Levon continue; 97*1f5207b7SJohn Levon if (insn->opcode != OP_PHI) 98*1f5207b7SJohn Levon continue; 99*1f5207b7SJohn Levon if (pseudo_in_list(target->needs, insn->target)) 100*1f5207b7SJohn Levon return 1; 101*1f5207b7SJohn Levon } END_FOR_EACH_PTR(insn); 102*1f5207b7SJohn Levon return 0; 103*1f5207b7SJohn Levon } 104*1f5207b7SJohn Levon 105*1f5207b7SJohn Levon /* 106*1f5207b7SJohn Levon * When we reach here, we have: 107*1f5207b7SJohn Levon * - a basic block that ends in a conditional branch and 108*1f5207b7SJohn Levon * that has no side effects apart from the pseudos it 109*1f5207b7SJohn Levon * may change. 110*1f5207b7SJohn Levon * - the phi-node that the conditional branch depends on 111*1f5207b7SJohn Levon * - full pseudo liveness information 112*1f5207b7SJohn Levon * 113*1f5207b7SJohn Levon * We need to check if any of the _sources_ of the phi-node 114*1f5207b7SJohn Levon * may be constant, and not actually need this block at all. 115*1f5207b7SJohn Levon */ 116*1f5207b7SJohn Levon static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first, struct instruction *second) 117*1f5207b7SJohn Levon { 118*1f5207b7SJohn Levon int changed = 0; 119*1f5207b7SJohn Levon pseudo_t phi; 120*1f5207b7SJohn Levon int bogus; 121*1f5207b7SJohn Levon 122*1f5207b7SJohn Levon /* 123*1f5207b7SJohn Levon * This a due to improper dominance tracking during 124*1f5207b7SJohn Levon * simplify_symbol_usage()/conversion to SSA form. 125*1f5207b7SJohn Levon * No sane simplification can be done when we have this. 126*1f5207b7SJohn Levon */ 127*1f5207b7SJohn Levon bogus = bb_list_size(bb->parents) != pseudo_list_size(first->phi_list); 128*1f5207b7SJohn Levon 129*1f5207b7SJohn Levon FOR_EACH_PTR(first->phi_list, phi) { 130*1f5207b7SJohn Levon struct instruction *def = phi->def; 131*1f5207b7SJohn Levon struct basic_block *source, *target; 132*1f5207b7SJohn Levon pseudo_t pseudo; 133*1f5207b7SJohn Levon struct instruction *br; 134*1f5207b7SJohn Levon int true; 135*1f5207b7SJohn Levon 136*1f5207b7SJohn Levon if (!def) 137*1f5207b7SJohn Levon continue; 138*1f5207b7SJohn Levon source = def->bb; 139*1f5207b7SJohn Levon pseudo = def->src1; 140*1f5207b7SJohn Levon if (!pseudo || !source) 141*1f5207b7SJohn Levon continue; 142*1f5207b7SJohn Levon br = last_instruction(source->insns); 143*1f5207b7SJohn Levon if (!br) 144*1f5207b7SJohn Levon continue; 145*1f5207b7SJohn Levon if (br->opcode != OP_CBR && br->opcode != OP_BR) 146*1f5207b7SJohn Levon continue; 147*1f5207b7SJohn Levon true = pseudo_truth_value(pseudo); 148*1f5207b7SJohn Levon if (true < 0) 149*1f5207b7SJohn Levon continue; 150*1f5207b7SJohn Levon target = true ? second->bb_true : second->bb_false; 151*1f5207b7SJohn Levon if (bb_depends_on(target, bb)) 152*1f5207b7SJohn Levon continue; 153*1f5207b7SJohn Levon if (bb_depends_on_phi(target, bb)) 154*1f5207b7SJohn Levon continue; 155*1f5207b7SJohn Levon changed |= rewrite_branch(source, &br->bb_true, bb, target); 156*1f5207b7SJohn Levon changed |= rewrite_branch(source, &br->bb_false, bb, target); 157*1f5207b7SJohn Levon if (changed && !bogus) 158*1f5207b7SJohn Levon kill_use(THIS_ADDRESS(phi)); 159*1f5207b7SJohn Levon } END_FOR_EACH_PTR(phi); 160*1f5207b7SJohn Levon return changed; 161*1f5207b7SJohn Levon } 162*1f5207b7SJohn Levon 163*1f5207b7SJohn Levon static int bb_has_side_effects(struct basic_block *bb) 164*1f5207b7SJohn Levon { 165*1f5207b7SJohn Levon struct instruction *insn; 166*1f5207b7SJohn Levon FOR_EACH_PTR(bb->insns, insn) { 167*1f5207b7SJohn Levon switch (insn->opcode) { 168*1f5207b7SJohn Levon case OP_CALL: 169*1f5207b7SJohn Levon /* FIXME! This should take "const" etc into account */ 170*1f5207b7SJohn Levon return 1; 171*1f5207b7SJohn Levon 172*1f5207b7SJohn Levon case OP_STORE: 173*1f5207b7SJohn Levon case OP_CONTEXT: 174*1f5207b7SJohn Levon return 1; 175*1f5207b7SJohn Levon 176*1f5207b7SJohn Levon case OP_ASM: 177*1f5207b7SJohn Levon /* FIXME! This should take "volatile" etc into account */ 178*1f5207b7SJohn Levon return 1; 179*1f5207b7SJohn Levon 180*1f5207b7SJohn Levon default: 181*1f5207b7SJohn Levon continue; 182*1f5207b7SJohn Levon } 183*1f5207b7SJohn Levon } END_FOR_EACH_PTR(insn); 184*1f5207b7SJohn Levon return 0; 185*1f5207b7SJohn Levon } 186*1f5207b7SJohn Levon 187*1f5207b7SJohn Levon static int simplify_phi_branch(struct basic_block *bb, struct instruction *br) 188*1f5207b7SJohn Levon { 189*1f5207b7SJohn Levon pseudo_t cond = br->cond; 190*1f5207b7SJohn Levon struct instruction *def; 191*1f5207b7SJohn Levon 192*1f5207b7SJohn Levon if (cond->type != PSEUDO_REG) 193*1f5207b7SJohn Levon return 0; 194*1f5207b7SJohn Levon def = cond->def; 195*1f5207b7SJohn Levon if (def->bb != bb || def->opcode != OP_PHI) 196*1f5207b7SJohn Levon return 0; 197*1f5207b7SJohn Levon if (bb_has_side_effects(bb)) 198*1f5207b7SJohn Levon return 0; 199*1f5207b7SJohn Levon return try_to_simplify_bb(bb, def, br); 200*1f5207b7SJohn Levon } 201*1f5207b7SJohn Levon 202*1f5207b7SJohn Levon static int simplify_branch_branch(struct basic_block *bb, struct instruction *br, 203*1f5207b7SJohn Levon struct basic_block **target_p, int true) 204*1f5207b7SJohn Levon { 205*1f5207b7SJohn Levon struct basic_block *target = *target_p, *final; 206*1f5207b7SJohn Levon struct instruction *insn; 207*1f5207b7SJohn Levon int retval; 208*1f5207b7SJohn Levon 209*1f5207b7SJohn Levon if (target == bb) 210*1f5207b7SJohn Levon return 0; 211*1f5207b7SJohn Levon insn = last_instruction(target->insns); 212*1f5207b7SJohn Levon if (!insn || insn->opcode != OP_CBR || insn->cond != br->cond) 213*1f5207b7SJohn Levon return 0; 214*1f5207b7SJohn Levon /* 215*1f5207b7SJohn Levon * Ahhah! We've found a branch to a branch on the same conditional! 216*1f5207b7SJohn Levon * Now we just need to see if we can rewrite the branch.. 217*1f5207b7SJohn Levon */ 218*1f5207b7SJohn Levon retval = 0; 219*1f5207b7SJohn Levon final = true ? insn->bb_true : insn->bb_false; 220*1f5207b7SJohn Levon if (bb_has_side_effects(target)) 221*1f5207b7SJohn Levon goto try_to_rewrite_target; 222*1f5207b7SJohn Levon if (bb_depends_on(final, target)) 223*1f5207b7SJohn Levon goto try_to_rewrite_target; 224*1f5207b7SJohn Levon if (bb_depends_on_phi(final, target)) 225*1f5207b7SJohn Levon return 0; 226*1f5207b7SJohn Levon return rewrite_branch(bb, target_p, target, final); 227*1f5207b7SJohn Levon 228*1f5207b7SJohn Levon try_to_rewrite_target: 229*1f5207b7SJohn Levon /* 230*1f5207b7SJohn Levon * If we're the only parent, at least we can rewrite the 231*1f5207b7SJohn Levon * now-known second branch. 232*1f5207b7SJohn Levon */ 233*1f5207b7SJohn Levon if (bb_list_size(target->parents) != 1) 234*1f5207b7SJohn Levon return retval; 235*1f5207b7SJohn Levon insert_branch(target, insn, final); 236*1f5207b7SJohn Levon return 1; 237*1f5207b7SJohn Levon } 238*1f5207b7SJohn Levon 239*1f5207b7SJohn Levon static int simplify_one_branch(struct basic_block *bb, struct instruction *br) 240*1f5207b7SJohn Levon { 241*1f5207b7SJohn Levon if (simplify_phi_branch(bb, br)) 242*1f5207b7SJohn Levon return 1; 243*1f5207b7SJohn Levon return simplify_branch_branch(bb, br, &br->bb_true, 1) | 244*1f5207b7SJohn Levon simplify_branch_branch(bb, br, &br->bb_false, 0); 245*1f5207b7SJohn Levon } 246*1f5207b7SJohn Levon 247*1f5207b7SJohn Levon static int simplify_branch_nodes(struct entrypoint *ep) 248*1f5207b7SJohn Levon { 249*1f5207b7SJohn Levon int changed = 0; 250*1f5207b7SJohn Levon struct basic_block *bb; 251*1f5207b7SJohn Levon 252*1f5207b7SJohn Levon FOR_EACH_PTR(ep->bbs, bb) { 253*1f5207b7SJohn Levon struct instruction *br = last_instruction(bb->insns); 254*1f5207b7SJohn Levon 255*1f5207b7SJohn Levon if (!br || br->opcode != OP_CBR) 256*1f5207b7SJohn Levon continue; 257*1f5207b7SJohn Levon changed |= simplify_one_branch(bb, br); 258*1f5207b7SJohn Levon } END_FOR_EACH_PTR(bb); 259*1f5207b7SJohn Levon return changed; 260*1f5207b7SJohn Levon } 261*1f5207b7SJohn Levon 262*1f5207b7SJohn Levon /* 263*1f5207b7SJohn Levon * This is called late - when we have intra-bb liveness information.. 264*1f5207b7SJohn Levon */ 265*1f5207b7SJohn Levon int simplify_flow(struct entrypoint *ep) 266*1f5207b7SJohn Levon { 267*1f5207b7SJohn Levon return simplify_branch_nodes(ep); 268*1f5207b7SJohn Levon } 269*1f5207b7SJohn Levon 270*1f5207b7SJohn Levon static inline void concat_user_list(struct pseudo_user_list *src, struct pseudo_user_list **dst) 271*1f5207b7SJohn Levon { 272*1f5207b7SJohn Levon concat_ptr_list((struct ptr_list *)src, (struct ptr_list **)dst); 273*1f5207b7SJohn Levon } 274*1f5207b7SJohn Levon 275*1f5207b7SJohn Levon void convert_instruction_target(struct instruction *insn, pseudo_t src) 276*1f5207b7SJohn Levon { 277*1f5207b7SJohn Levon pseudo_t target; 278*1f5207b7SJohn Levon struct pseudo_user *pu; 279*1f5207b7SJohn Levon /* 280*1f5207b7SJohn Levon * Go through the "insn->users" list and replace them all.. 281*1f5207b7SJohn Levon */ 282*1f5207b7SJohn Levon target = insn->target; 283*1f5207b7SJohn Levon if (target == src) 284*1f5207b7SJohn Levon return; 285*1f5207b7SJohn Levon FOR_EACH_PTR(target->users, pu) { 286*1f5207b7SJohn Levon if (*pu->userp != VOID) { 287*1f5207b7SJohn Levon assert(*pu->userp == target); 288*1f5207b7SJohn Levon *pu->userp = src; 289*1f5207b7SJohn Levon } 290*1f5207b7SJohn Levon } END_FOR_EACH_PTR(pu); 291*1f5207b7SJohn Levon if (has_use_list(src)) 292*1f5207b7SJohn Levon concat_user_list(target->users, &src->users); 293*1f5207b7SJohn Levon target->users = NULL; 294*1f5207b7SJohn Levon } 295*1f5207b7SJohn Levon 296*1f5207b7SJohn Levon void convert_load_instruction(struct instruction *insn, pseudo_t src) 297*1f5207b7SJohn Levon { 298*1f5207b7SJohn Levon convert_instruction_target(insn, src); 299*1f5207b7SJohn Levon /* Turn the load into a no-op */ 300*1f5207b7SJohn Levon insn->opcode = OP_LNOP; 301*1f5207b7SJohn Levon insn->bb = NULL; 302*1f5207b7SJohn Levon } 303*1f5207b7SJohn Levon 304*1f5207b7SJohn Levon static int overlapping_memop(struct instruction *a, struct instruction *b) 305*1f5207b7SJohn Levon { 306*1f5207b7SJohn Levon unsigned int a_start = bytes_to_bits(a->offset); 307*1f5207b7SJohn Levon unsigned int b_start = bytes_to_bits(b->offset); 308*1f5207b7SJohn Levon unsigned int a_size = a->size; 309*1f5207b7SJohn Levon unsigned int b_size = b->size; 310*1f5207b7SJohn Levon 311*1f5207b7SJohn Levon if (a_size + a_start <= b_start) 312*1f5207b7SJohn Levon return 0; 313*1f5207b7SJohn Levon if (b_size + b_start <= a_start) 314*1f5207b7SJohn Levon return 0; 315*1f5207b7SJohn Levon return 1; 316*1f5207b7SJohn Levon } 317*1f5207b7SJohn Levon 318*1f5207b7SJohn Levon static inline int same_memop(struct instruction *a, struct instruction *b) 319*1f5207b7SJohn Levon { 320*1f5207b7SJohn Levon return a->offset == b->offset && a->size == b->size; 321*1f5207b7SJohn Levon } 322*1f5207b7SJohn Levon 323*1f5207b7SJohn Levon static inline int distinct_symbols(pseudo_t a, pseudo_t b) 324*1f5207b7SJohn Levon { 325*1f5207b7SJohn Levon if (a->type != PSEUDO_SYM) 326*1f5207b7SJohn Levon return 0; 327*1f5207b7SJohn Levon if (b->type != PSEUDO_SYM) 328*1f5207b7SJohn Levon return 0; 329*1f5207b7SJohn Levon return a->sym != b->sym; 330*1f5207b7SJohn Levon } 331*1f5207b7SJohn Levon 332*1f5207b7SJohn Levon /* 333*1f5207b7SJohn Levon * Return 1 if "dom" dominates the access to "pseudo" 334*1f5207b7SJohn Levon * in "insn". 335*1f5207b7SJohn Levon * 336*1f5207b7SJohn Levon * Return 0 if it doesn't, and -1 if you don't know. 337*1f5207b7SJohn Levon */ 338*1f5207b7SJohn Levon int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom, int local) 339*1f5207b7SJohn Levon { 340*1f5207b7SJohn Levon int opcode = dom->opcode; 341*1f5207b7SJohn Levon 342*1f5207b7SJohn Levon if (opcode == OP_CALL || opcode == OP_ENTRY) 343*1f5207b7SJohn Levon return local ? 0 : -1; 344*1f5207b7SJohn Levon if (opcode != OP_LOAD && opcode != OP_STORE) 345*1f5207b7SJohn Levon return 0; 346*1f5207b7SJohn Levon if (dom->src != pseudo) { 347*1f5207b7SJohn Levon if (local) 348*1f5207b7SJohn Levon return 0; 349*1f5207b7SJohn Levon /* We don't think two explicitly different symbols ever alias */ 350*1f5207b7SJohn Levon if (distinct_symbols(insn->src, dom->src)) 351*1f5207b7SJohn Levon return 0; 352*1f5207b7SJohn Levon /* We could try to do some alias analysis here */ 353*1f5207b7SJohn Levon return -1; 354*1f5207b7SJohn Levon } 355*1f5207b7SJohn Levon if (!same_memop(insn, dom)) { 356*1f5207b7SJohn Levon if (dom->opcode == OP_LOAD) 357*1f5207b7SJohn Levon return 0; 358*1f5207b7SJohn Levon if (!overlapping_memop(insn, dom)) 359*1f5207b7SJohn Levon return 0; 360*1f5207b7SJohn Levon return -1; 361*1f5207b7SJohn Levon } 362*1f5207b7SJohn Levon return 1; 363*1f5207b7SJohn Levon } 364*1f5207b7SJohn Levon 365*1f5207b7SJohn Levon static int phisrc_in_bb(struct pseudo_list *list, struct basic_block *bb) 366*1f5207b7SJohn Levon { 367*1f5207b7SJohn Levon pseudo_t p; 368*1f5207b7SJohn Levon FOR_EACH_PTR(list, p) { 369*1f5207b7SJohn Levon if (p->def->bb == bb) 370*1f5207b7SJohn Levon return 1; 371*1f5207b7SJohn Levon } END_FOR_EACH_PTR(p); 372*1f5207b7SJohn Levon 373*1f5207b7SJohn Levon return 0; 374*1f5207b7SJohn Levon } 375*1f5207b7SJohn Levon 376*1f5207b7SJohn Levon static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn, 377*1f5207b7SJohn Levon struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators, 378*1f5207b7SJohn Levon int local) 379*1f5207b7SJohn Levon { 380*1f5207b7SJohn Levon struct basic_block *parent; 381*1f5207b7SJohn Levon 382*1f5207b7SJohn Levon if (!bb->parents) 383*1f5207b7SJohn Levon return !!local; 384*1f5207b7SJohn Levon 385*1f5207b7SJohn Levon FOR_EACH_PTR(bb->parents, parent) { 386*1f5207b7SJohn Levon struct instruction *one; 387*1f5207b7SJohn Levon struct instruction *br; 388*1f5207b7SJohn Levon pseudo_t phi; 389*1f5207b7SJohn Levon 390*1f5207b7SJohn Levon FOR_EACH_PTR_REVERSE(parent->insns, one) { 391*1f5207b7SJohn Levon int dominance; 392*1f5207b7SJohn Levon if (one == insn) 393*1f5207b7SJohn Levon goto no_dominance; 394*1f5207b7SJohn Levon dominance = dominates(pseudo, insn, one, local); 395*1f5207b7SJohn Levon if (dominance < 0) { 396*1f5207b7SJohn Levon if (one->opcode == OP_LOAD) 397*1f5207b7SJohn Levon continue; 398*1f5207b7SJohn Levon return 0; 399*1f5207b7SJohn Levon } 400*1f5207b7SJohn Levon if (!dominance) 401*1f5207b7SJohn Levon continue; 402*1f5207b7SJohn Levon goto found_dominator; 403*1f5207b7SJohn Levon } END_FOR_EACH_PTR_REVERSE(one); 404*1f5207b7SJohn Levon no_dominance: 405*1f5207b7SJohn Levon if (parent->generation == generation) 406*1f5207b7SJohn Levon continue; 407*1f5207b7SJohn Levon parent->generation = generation; 408*1f5207b7SJohn Levon 409*1f5207b7SJohn Levon if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local)) 410*1f5207b7SJohn Levon return 0; 411*1f5207b7SJohn Levon continue; 412*1f5207b7SJohn Levon 413*1f5207b7SJohn Levon found_dominator: 414*1f5207b7SJohn Levon if (dominators && phisrc_in_bb(*dominators, parent)) 415*1f5207b7SJohn Levon continue; 416*1f5207b7SJohn Levon br = delete_last_instruction(&parent->insns); 417*1f5207b7SJohn Levon phi = alloc_phi(parent, one->target, one->size); 418*1f5207b7SJohn Levon phi->ident = phi->ident ? : pseudo->ident; 419*1f5207b7SJohn Levon add_instruction(&parent->insns, br); 420*1f5207b7SJohn Levon use_pseudo(insn, phi, add_pseudo(dominators, phi)); 421*1f5207b7SJohn Levon } END_FOR_EACH_PTR(parent); 422*1f5207b7SJohn Levon return 1; 423*1f5207b7SJohn Levon } 424*1f5207b7SJohn Levon 425*1f5207b7SJohn Levon /* 426*1f5207b7SJohn Levon * We should probably sort the phi list just to make it easier to compare 427*1f5207b7SJohn Levon * later for equality. 428*1f5207b7SJohn Levon */ 429*1f5207b7SJohn Levon void rewrite_load_instruction(struct instruction *insn, struct pseudo_list *dominators) 430*1f5207b7SJohn Levon { 431*1f5207b7SJohn Levon pseudo_t new, phi; 432*1f5207b7SJohn Levon 433*1f5207b7SJohn Levon /* 434*1f5207b7SJohn Levon * Check for somewhat common case of duplicate 435*1f5207b7SJohn Levon * phi nodes. 436*1f5207b7SJohn Levon */ 437*1f5207b7SJohn Levon new = first_pseudo(dominators)->def->src1; 438*1f5207b7SJohn Levon FOR_EACH_PTR(dominators, phi) { 439*1f5207b7SJohn Levon if (new != phi->def->src1) 440*1f5207b7SJohn Levon goto complex_phi; 441*1f5207b7SJohn Levon new->ident = new->ident ? : phi->ident; 442*1f5207b7SJohn Levon } END_FOR_EACH_PTR(phi); 443*1f5207b7SJohn Levon 444*1f5207b7SJohn Levon /* 445*1f5207b7SJohn Levon * All the same pseudo - mark the phi-nodes unused 446*1f5207b7SJohn Levon * and convert the load into a LNOP and replace the 447*1f5207b7SJohn Levon * pseudo. 448*1f5207b7SJohn Levon */ 449*1f5207b7SJohn Levon FOR_EACH_PTR(dominators, phi) { 450*1f5207b7SJohn Levon kill_instruction(phi->def); 451*1f5207b7SJohn Levon } END_FOR_EACH_PTR(phi); 452*1f5207b7SJohn Levon convert_load_instruction(insn, new); 453*1f5207b7SJohn Levon return; 454*1f5207b7SJohn Levon 455*1f5207b7SJohn Levon complex_phi: 456*1f5207b7SJohn Levon /* We leave symbol pseudos with a bogus usage list here */ 457*1f5207b7SJohn Levon if (insn->src->type != PSEUDO_SYM) 458*1f5207b7SJohn Levon kill_use(&insn->src); 459*1f5207b7SJohn Levon insn->opcode = OP_PHI; 460*1f5207b7SJohn Levon insn->phi_list = dominators; 461*1f5207b7SJohn Levon } 462*1f5207b7SJohn Levon 463*1f5207b7SJohn Levon static int find_dominating_stores(pseudo_t pseudo, struct instruction *insn, 464*1f5207b7SJohn Levon unsigned long generation, int local) 465*1f5207b7SJohn Levon { 466*1f5207b7SJohn Levon struct basic_block *bb = insn->bb; 467*1f5207b7SJohn Levon struct instruction *one, *dom = NULL; 468*1f5207b7SJohn Levon struct pseudo_list *dominators; 469*1f5207b7SJohn Levon int partial; 470*1f5207b7SJohn Levon 471*1f5207b7SJohn Levon /* Unreachable load? Undo it */ 472*1f5207b7SJohn Levon if (!bb) { 473*1f5207b7SJohn Levon insn->opcode = OP_LNOP; 474*1f5207b7SJohn Levon return 1; 475*1f5207b7SJohn Levon } 476*1f5207b7SJohn Levon 477*1f5207b7SJohn Levon partial = 0; 478*1f5207b7SJohn Levon FOR_EACH_PTR(bb->insns, one) { 479*1f5207b7SJohn Levon int dominance; 480*1f5207b7SJohn Levon if (one == insn) 481*1f5207b7SJohn Levon goto found; 482*1f5207b7SJohn Levon dominance = dominates(pseudo, insn, one, local); 483*1f5207b7SJohn Levon if (dominance < 0) { 484*1f5207b7SJohn Levon /* Ignore partial load dominators */ 485*1f5207b7SJohn Levon if (one->opcode == OP_LOAD) 486*1f5207b7SJohn Levon continue; 487*1f5207b7SJohn Levon dom = NULL; 488*1f5207b7SJohn Levon partial = 1; 489*1f5207b7SJohn Levon continue; 490*1f5207b7SJohn Levon } 491*1f5207b7SJohn Levon if (!dominance) 492*1f5207b7SJohn Levon continue; 493*1f5207b7SJohn Levon dom = one; 494*1f5207b7SJohn Levon partial = 0; 495*1f5207b7SJohn Levon } END_FOR_EACH_PTR(one); 496*1f5207b7SJohn Levon /* Whaa? */ 497*1f5207b7SJohn Levon warning(pseudo->sym->pos, "unable to find symbol read"); 498*1f5207b7SJohn Levon return 0; 499*1f5207b7SJohn Levon found: 500*1f5207b7SJohn Levon if (partial) 501*1f5207b7SJohn Levon return 0; 502*1f5207b7SJohn Levon 503*1f5207b7SJohn Levon if (dom) { 504*1f5207b7SJohn Levon convert_load_instruction(insn, dom->target); 505*1f5207b7SJohn Levon return 1; 506*1f5207b7SJohn Levon } 507*1f5207b7SJohn Levon 508*1f5207b7SJohn Levon /* OK, go find the parents */ 509*1f5207b7SJohn Levon bb->generation = generation; 510*1f5207b7SJohn Levon 511*1f5207b7SJohn Levon dominators = NULL; 512*1f5207b7SJohn Levon if (!find_dominating_parents(pseudo, insn, bb, generation, &dominators, local)) 513*1f5207b7SJohn Levon return 0; 514*1f5207b7SJohn Levon 515*1f5207b7SJohn Levon /* This happens with initial assignments to structures etc.. */ 516*1f5207b7SJohn Levon if (!dominators) { 517*1f5207b7SJohn Levon if (!local) 518*1f5207b7SJohn Levon return 0; 519*1f5207b7SJohn Levon check_access(insn); 520*1f5207b7SJohn Levon convert_load_instruction(insn, value_pseudo(insn->type, 0)); 521*1f5207b7SJohn Levon return 1; 522*1f5207b7SJohn Levon } 523*1f5207b7SJohn Levon 524*1f5207b7SJohn Levon /* 525*1f5207b7SJohn Levon * If we find just one dominating instruction, we 526*1f5207b7SJohn Levon * can turn it into a direct thing. Otherwise we'll 527*1f5207b7SJohn Levon * have to turn the load into a phi-node of the 528*1f5207b7SJohn Levon * dominators. 529*1f5207b7SJohn Levon */ 530*1f5207b7SJohn Levon rewrite_load_instruction(insn, dominators); 531*1f5207b7SJohn Levon return 1; 532*1f5207b7SJohn Levon } 533*1f5207b7SJohn Levon 534*1f5207b7SJohn Levon static void kill_store(struct instruction *insn) 535*1f5207b7SJohn Levon { 536*1f5207b7SJohn Levon if (insn) { 537*1f5207b7SJohn Levon insn->bb = NULL; 538*1f5207b7SJohn Levon insn->opcode = OP_SNOP; 539*1f5207b7SJohn Levon kill_use(&insn->target); 540*1f5207b7SJohn Levon } 541*1f5207b7SJohn Levon } 542*1f5207b7SJohn Levon 543*1f5207b7SJohn Levon /* Kill a pseudo that is dead on exit from the bb */ 544*1f5207b7SJohn Levon static void kill_dead_stores(pseudo_t pseudo, unsigned long generation, struct basic_block *bb, int local) 545*1f5207b7SJohn Levon { 546*1f5207b7SJohn Levon struct instruction *insn; 547*1f5207b7SJohn Levon struct basic_block *parent; 548*1f5207b7SJohn Levon 549*1f5207b7SJohn Levon if (bb->generation == generation) 550*1f5207b7SJohn Levon return; 551*1f5207b7SJohn Levon bb->generation = generation; 552*1f5207b7SJohn Levon FOR_EACH_PTR_REVERSE(bb->insns, insn) { 553*1f5207b7SJohn Levon int opcode = insn->opcode; 554*1f5207b7SJohn Levon 555*1f5207b7SJohn Levon if (opcode != OP_LOAD && opcode != OP_STORE) { 556*1f5207b7SJohn Levon if (local) 557*1f5207b7SJohn Levon continue; 558*1f5207b7SJohn Levon if (opcode == OP_CALL) 559*1f5207b7SJohn Levon return; 560*1f5207b7SJohn Levon continue; 561*1f5207b7SJohn Levon } 562*1f5207b7SJohn Levon if (insn->src == pseudo) { 563*1f5207b7SJohn Levon if (opcode == OP_LOAD) 564*1f5207b7SJohn Levon return; 565*1f5207b7SJohn Levon kill_store(insn); 566*1f5207b7SJohn Levon continue; 567*1f5207b7SJohn Levon } 568*1f5207b7SJohn Levon if (local) 569*1f5207b7SJohn Levon continue; 570*1f5207b7SJohn Levon if (insn->src->type != PSEUDO_SYM) 571*1f5207b7SJohn Levon return; 572*1f5207b7SJohn Levon } END_FOR_EACH_PTR_REVERSE(insn); 573*1f5207b7SJohn Levon 574*1f5207b7SJohn Levon FOR_EACH_PTR(bb->parents, parent) { 575*1f5207b7SJohn Levon struct basic_block *child; 576*1f5207b7SJohn Levon FOR_EACH_PTR(parent->children, child) { 577*1f5207b7SJohn Levon if (child && child != bb) 578*1f5207b7SJohn Levon return; 579*1f5207b7SJohn Levon } END_FOR_EACH_PTR(child); 580*1f5207b7SJohn Levon kill_dead_stores(pseudo, generation, parent, local); 581*1f5207b7SJohn Levon } END_FOR_EACH_PTR(parent); 582*1f5207b7SJohn Levon } 583*1f5207b7SJohn Levon 584*1f5207b7SJohn Levon /* 585*1f5207b7SJohn Levon * This should see if the "insn" trivially dominates some previous store, and kill the 586*1f5207b7SJohn Levon * store if unnecessary. 587*1f5207b7SJohn Levon */ 588*1f5207b7SJohn Levon static void kill_dominated_stores(pseudo_t pseudo, struct instruction *insn, 589*1f5207b7SJohn Levon unsigned long generation, struct basic_block *bb, int local, int found) 590*1f5207b7SJohn Levon { 591*1f5207b7SJohn Levon struct instruction *one; 592*1f5207b7SJohn Levon struct basic_block *parent; 593*1f5207b7SJohn Levon 594*1f5207b7SJohn Levon /* Unreachable store? Undo it */ 595*1f5207b7SJohn Levon if (!bb) { 596*1f5207b7SJohn Levon kill_store(insn); 597*1f5207b7SJohn Levon return; 598*1f5207b7SJohn Levon } 599*1f5207b7SJohn Levon if (bb->generation == generation) 600*1f5207b7SJohn Levon return; 601*1f5207b7SJohn Levon bb->generation = generation; 602*1f5207b7SJohn Levon FOR_EACH_PTR_REVERSE(bb->insns, one) { 603*1f5207b7SJohn Levon int dominance; 604*1f5207b7SJohn Levon if (!found) { 605*1f5207b7SJohn Levon if (one != insn) 606*1f5207b7SJohn Levon continue; 607*1f5207b7SJohn Levon found = 1; 608*1f5207b7SJohn Levon continue; 609*1f5207b7SJohn Levon } 610*1f5207b7SJohn Levon dominance = dominates(pseudo, insn, one, local); 611*1f5207b7SJohn Levon if (!dominance) 612*1f5207b7SJohn Levon continue; 613*1f5207b7SJohn Levon if (dominance < 0) 614*1f5207b7SJohn Levon return; 615*1f5207b7SJohn Levon if (one->opcode == OP_LOAD) 616*1f5207b7SJohn Levon return; 617*1f5207b7SJohn Levon kill_store(one); 618*1f5207b7SJohn Levon } END_FOR_EACH_PTR_REVERSE(one); 619*1f5207b7SJohn Levon 620*1f5207b7SJohn Levon if (!found) { 621*1f5207b7SJohn Levon warning(bb->pos, "Unable to find instruction"); 622*1f5207b7SJohn Levon return; 623*1f5207b7SJohn Levon } 624*1f5207b7SJohn Levon 625*1f5207b7SJohn Levon FOR_EACH_PTR(bb->parents, parent) { 626*1f5207b7SJohn Levon struct basic_block *child; 627*1f5207b7SJohn Levon FOR_EACH_PTR(parent->children, child) { 628*1f5207b7SJohn Levon if (child && child != bb) 629*1f5207b7SJohn Levon return; 630*1f5207b7SJohn Levon } END_FOR_EACH_PTR(child); 631*1f5207b7SJohn Levon kill_dominated_stores(pseudo, insn, generation, parent, local, found); 632*1f5207b7SJohn Levon } END_FOR_EACH_PTR(parent); 633*1f5207b7SJohn Levon } 634*1f5207b7SJohn Levon 635*1f5207b7SJohn Levon void check_access(struct instruction *insn) 636*1f5207b7SJohn Levon { 637*1f5207b7SJohn Levon pseudo_t pseudo = insn->src; 638*1f5207b7SJohn Levon 639*1f5207b7SJohn Levon if (insn->bb && pseudo->type == PSEUDO_SYM) { 640*1f5207b7SJohn Levon int offset = insn->offset, bit = bytes_to_bits(offset) + insn->size; 641*1f5207b7SJohn Levon struct symbol *sym = pseudo->sym; 642*1f5207b7SJohn Levon 643*1f5207b7SJohn Levon if (sym->bit_size > 0 && (offset < 0 || bit > sym->bit_size)) 644*1f5207b7SJohn Levon warning(insn->pos, "invalid access %s '%s' (%d %d)", 645*1f5207b7SJohn Levon offset < 0 ? "below" : "past the end of", 646*1f5207b7SJohn Levon show_ident(sym->ident), offset, 647*1f5207b7SJohn Levon bits_to_bytes(sym->bit_size)); 648*1f5207b7SJohn Levon } 649*1f5207b7SJohn Levon } 650*1f5207b7SJohn Levon 651*1f5207b7SJohn Levon static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym) 652*1f5207b7SJohn Levon { 653*1f5207b7SJohn Levon pseudo_t pseudo; 654*1f5207b7SJohn Levon struct pseudo_user *pu; 655*1f5207b7SJohn Levon unsigned long mod; 656*1f5207b7SJohn Levon int all; 657*1f5207b7SJohn Levon 658*1f5207b7SJohn Levon /* Never used as a symbol? */ 659*1f5207b7SJohn Levon pseudo = sym->pseudo; 660*1f5207b7SJohn Levon if (!pseudo) 661*1f5207b7SJohn Levon return; 662*1f5207b7SJohn Levon 663*1f5207b7SJohn Levon /* We don't do coverage analysis of volatiles.. */ 664*1f5207b7SJohn Levon if (sym->ctype.modifiers & MOD_VOLATILE) 665*1f5207b7SJohn Levon return; 666*1f5207b7SJohn Levon 667*1f5207b7SJohn Levon /* ..and symbols with external visibility need more care */ 668*1f5207b7SJohn Levon mod = sym->ctype.modifiers & (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE); 669*1f5207b7SJohn Levon if (mod) 670*1f5207b7SJohn Levon goto external_visibility; 671*1f5207b7SJohn Levon 672*1f5207b7SJohn Levon FOR_EACH_PTR(pseudo->users, pu) { 673*1f5207b7SJohn Levon /* We know that the symbol-pseudo use is the "src" in the instruction */ 674*1f5207b7SJohn Levon struct instruction *insn = pu->insn; 675*1f5207b7SJohn Levon 676*1f5207b7SJohn Levon switch (insn->opcode) { 677*1f5207b7SJohn Levon case OP_STORE: 678*1f5207b7SJohn Levon break; 679*1f5207b7SJohn Levon case OP_LOAD: 680*1f5207b7SJohn Levon break; 681*1f5207b7SJohn Levon case OP_SYMADDR: 682*1f5207b7SJohn Levon if (!insn->bb) 683*1f5207b7SJohn Levon continue; 684*1f5207b7SJohn Levon mod |= MOD_ADDRESSABLE; 685*1f5207b7SJohn Levon goto external_visibility; 686*1f5207b7SJohn Levon case OP_NOP: 687*1f5207b7SJohn Levon case OP_SNOP: 688*1f5207b7SJohn Levon case OP_LNOP: 689*1f5207b7SJohn Levon case OP_PHI: 690*1f5207b7SJohn Levon continue; 691*1f5207b7SJohn Levon default: 692*1f5207b7SJohn Levon warning(sym->pos, "symbol '%s' pseudo used in unexpected way", show_ident(sym->ident)); 693*1f5207b7SJohn Levon } 694*1f5207b7SJohn Levon } END_FOR_EACH_PTR(pu); 695*1f5207b7SJohn Levon 696*1f5207b7SJohn Levon external_visibility: 697*1f5207b7SJohn Levon all = 1; 698*1f5207b7SJohn Levon FOR_EACH_PTR_REVERSE(pseudo->users, pu) { 699*1f5207b7SJohn Levon struct instruction *insn = pu->insn; 700*1f5207b7SJohn Levon if (insn->opcode == OP_LOAD) 701*1f5207b7SJohn Levon all &= find_dominating_stores(pseudo, insn, ++bb_generation, !mod); 702*1f5207b7SJohn Levon } END_FOR_EACH_PTR_REVERSE(pu); 703*1f5207b7SJohn Levon 704*1f5207b7SJohn Levon /* If we converted all the loads, remove the stores. They are dead */ 705*1f5207b7SJohn Levon if (all && !mod) { 706*1f5207b7SJohn Levon FOR_EACH_PTR(pseudo->users, pu) { 707*1f5207b7SJohn Levon struct instruction *insn = pu->insn; 708*1f5207b7SJohn Levon if (insn->opcode == OP_STORE) 709*1f5207b7SJohn Levon kill_store(insn); 710*1f5207b7SJohn Levon } END_FOR_EACH_PTR(pu); 711*1f5207b7SJohn Levon } else { 712*1f5207b7SJohn Levon /* 713*1f5207b7SJohn Levon * If we couldn't take the shortcut, see if we can at least kill some 714*1f5207b7SJohn Levon * of them.. 715*1f5207b7SJohn Levon */ 716*1f5207b7SJohn Levon FOR_EACH_PTR(pseudo->users, pu) { 717*1f5207b7SJohn Levon struct instruction *insn = pu->insn; 718*1f5207b7SJohn Levon if (insn->opcode == OP_STORE) 719*1f5207b7SJohn Levon kill_dominated_stores(pseudo, insn, ++bb_generation, insn->bb, !mod, 0); 720*1f5207b7SJohn Levon } END_FOR_EACH_PTR(pu); 721*1f5207b7SJohn Levon 722*1f5207b7SJohn Levon if (!(mod & (MOD_NONLOCAL | MOD_STATIC))) { 723*1f5207b7SJohn Levon struct basic_block *bb; 724*1f5207b7SJohn Levon FOR_EACH_PTR(ep->bbs, bb) { 725*1f5207b7SJohn Levon if (!bb->children) 726*1f5207b7SJohn Levon kill_dead_stores(pseudo, ++bb_generation, bb, !mod); 727*1f5207b7SJohn Levon } END_FOR_EACH_PTR(bb); 728*1f5207b7SJohn Levon } 729*1f5207b7SJohn Levon } 730*1f5207b7SJohn Levon 731*1f5207b7SJohn Levon return; 732*1f5207b7SJohn Levon } 733*1f5207b7SJohn Levon 734*1f5207b7SJohn Levon void simplify_symbol_usage(struct entrypoint *ep) 735*1f5207b7SJohn Levon { 736*1f5207b7SJohn Levon pseudo_t pseudo; 737*1f5207b7SJohn Levon 738*1f5207b7SJohn Levon FOR_EACH_PTR(ep->accesses, pseudo) { 739*1f5207b7SJohn Levon simplify_one_symbol(ep, pseudo->sym); 740*1f5207b7SJohn Levon } END_FOR_EACH_PTR(pseudo); 741*1f5207b7SJohn Levon } 742*1f5207b7SJohn Levon 743*1f5207b7SJohn Levon static void mark_bb_reachable(struct basic_block *bb, unsigned long generation) 744*1f5207b7SJohn Levon { 745*1f5207b7SJohn Levon struct basic_block *child; 746*1f5207b7SJohn Levon 747*1f5207b7SJohn Levon if (bb->generation == generation) 748*1f5207b7SJohn Levon return; 749*1f5207b7SJohn Levon bb->generation = generation; 750*1f5207b7SJohn Levon FOR_EACH_PTR(bb->children, child) { 751*1f5207b7SJohn Levon mark_bb_reachable(child, generation); 752*1f5207b7SJohn Levon } END_FOR_EACH_PTR(child); 753*1f5207b7SJohn Levon } 754*1f5207b7SJohn Levon 755*1f5207b7SJohn Levon static void kill_defs(struct instruction *insn) 756*1f5207b7SJohn Levon { 757*1f5207b7SJohn Levon pseudo_t target = insn->target; 758*1f5207b7SJohn Levon 759*1f5207b7SJohn Levon if (!has_use_list(target)) 760*1f5207b7SJohn Levon return; 761*1f5207b7SJohn Levon if (target->def != insn) 762*1f5207b7SJohn Levon return; 763*1f5207b7SJohn Levon 764*1f5207b7SJohn Levon convert_instruction_target(insn, VOID); 765*1f5207b7SJohn Levon } 766*1f5207b7SJohn Levon 767*1f5207b7SJohn Levon void kill_bb(struct basic_block *bb) 768*1f5207b7SJohn Levon { 769*1f5207b7SJohn Levon struct instruction *insn; 770*1f5207b7SJohn Levon struct basic_block *child, *parent; 771*1f5207b7SJohn Levon 772*1f5207b7SJohn Levon FOR_EACH_PTR(bb->insns, insn) { 773*1f5207b7SJohn Levon kill_instruction_force(insn); 774*1f5207b7SJohn Levon kill_defs(insn); 775*1f5207b7SJohn Levon /* 776*1f5207b7SJohn Levon * We kill unreachable instructions even if they 777*1f5207b7SJohn Levon * otherwise aren't "killable" (e.g. volatile loads) 778*1f5207b7SJohn Levon */ 779*1f5207b7SJohn Levon } END_FOR_EACH_PTR(insn); 780*1f5207b7SJohn Levon bb->insns = NULL; 781*1f5207b7SJohn Levon 782*1f5207b7SJohn Levon FOR_EACH_PTR(bb->children, child) { 783*1f5207b7SJohn Levon remove_bb_from_list(&child->parents, bb, 0); 784*1f5207b7SJohn Levon } END_FOR_EACH_PTR(child); 785*1f5207b7SJohn Levon bb->children = NULL; 786*1f5207b7SJohn Levon 787*1f5207b7SJohn Levon FOR_EACH_PTR(bb->parents, parent) { 788*1f5207b7SJohn Levon remove_bb_from_list(&parent->children, bb, 0); 789*1f5207b7SJohn Levon } END_FOR_EACH_PTR(parent); 790*1f5207b7SJohn Levon bb->parents = NULL; 791*1f5207b7SJohn Levon } 792*1f5207b7SJohn Levon 793*1f5207b7SJohn Levon void kill_unreachable_bbs(struct entrypoint *ep) 794*1f5207b7SJohn Levon { 795*1f5207b7SJohn Levon struct basic_block *bb; 796*1f5207b7SJohn Levon unsigned long generation = ++bb_generation; 797*1f5207b7SJohn Levon 798*1f5207b7SJohn Levon mark_bb_reachable(ep->entry->bb, generation); 799*1f5207b7SJohn Levon FOR_EACH_PTR(ep->bbs, bb) { 800*1f5207b7SJohn Levon if (bb->generation == generation) 801*1f5207b7SJohn Levon continue; 802*1f5207b7SJohn Levon /* Mark it as being dead */ 803*1f5207b7SJohn Levon kill_bb(bb); 804*1f5207b7SJohn Levon bb->ep = NULL; 805*1f5207b7SJohn Levon DELETE_CURRENT_PTR(bb); 806*1f5207b7SJohn Levon } END_FOR_EACH_PTR(bb); 807*1f5207b7SJohn Levon PACK_PTR_LIST(&ep->bbs); 808*1f5207b7SJohn Levon } 809*1f5207b7SJohn Levon 810*1f5207b7SJohn Levon static int rewrite_parent_branch(struct basic_block *bb, struct basic_block *old, struct basic_block *new) 811*1f5207b7SJohn Levon { 812*1f5207b7SJohn Levon int changed = 0; 813*1f5207b7SJohn Levon struct instruction *insn = last_instruction(bb->insns); 814*1f5207b7SJohn Levon 815*1f5207b7SJohn Levon if (!insn) 816*1f5207b7SJohn Levon return 0; 817*1f5207b7SJohn Levon 818*1f5207b7SJohn Levon /* Infinite loops: let's not "optimize" them.. */ 819*1f5207b7SJohn Levon if (old == new) 820*1f5207b7SJohn Levon return 0; 821*1f5207b7SJohn Levon 822*1f5207b7SJohn Levon switch (insn->opcode) { 823*1f5207b7SJohn Levon case OP_CBR: 824*1f5207b7SJohn Levon changed |= rewrite_branch(bb, &insn->bb_false, old, new); 825*1f5207b7SJohn Levon /* fall through */ 826*1f5207b7SJohn Levon case OP_BR: 827*1f5207b7SJohn Levon changed |= rewrite_branch(bb, &insn->bb_true, old, new); 828*1f5207b7SJohn Levon assert(changed); 829*1f5207b7SJohn Levon return changed; 830*1f5207b7SJohn Levon case OP_SWITCH: { 831*1f5207b7SJohn Levon struct multijmp *jmp; 832*1f5207b7SJohn Levon FOR_EACH_PTR(insn->multijmp_list, jmp) { 833*1f5207b7SJohn Levon changed |= rewrite_branch(bb, &jmp->target, old, new); 834*1f5207b7SJohn Levon } END_FOR_EACH_PTR(jmp); 835*1f5207b7SJohn Levon assert(changed); 836*1f5207b7SJohn Levon return changed; 837*1f5207b7SJohn Levon } 838*1f5207b7SJohn Levon default: 839*1f5207b7SJohn Levon return 0; 840*1f5207b7SJohn Levon } 841*1f5207b7SJohn Levon } 842*1f5207b7SJohn Levon 843*1f5207b7SJohn Levon static struct basic_block * rewrite_branch_bb(struct basic_block *bb, struct instruction *br) 844*1f5207b7SJohn Levon { 845*1f5207b7SJohn Levon struct basic_block *parent; 846*1f5207b7SJohn Levon struct basic_block *target = br->bb_true; 847*1f5207b7SJohn Levon struct basic_block *false = br->bb_false; 848*1f5207b7SJohn Levon 849*1f5207b7SJohn Levon if (br->opcode == OP_CBR) { 850*1f5207b7SJohn Levon pseudo_t cond = br->cond; 851*1f5207b7SJohn Levon if (cond->type != PSEUDO_VAL) 852*1f5207b7SJohn Levon return NULL; 853*1f5207b7SJohn Levon target = cond->value ? target : false; 854*1f5207b7SJohn Levon } 855*1f5207b7SJohn Levon 856*1f5207b7SJohn Levon /* 857*1f5207b7SJohn Levon * We can't do FOR_EACH_PTR() here, because the parent list 858*1f5207b7SJohn Levon * may change when we rewrite the parent. 859*1f5207b7SJohn Levon */ 860*1f5207b7SJohn Levon while ((parent = first_basic_block(bb->parents)) != NULL) { 861*1f5207b7SJohn Levon if (!rewrite_parent_branch(parent, bb, target)) 862*1f5207b7SJohn Levon return NULL; 863*1f5207b7SJohn Levon } 864*1f5207b7SJohn Levon return target; 865*1f5207b7SJohn Levon } 866*1f5207b7SJohn Levon 867*1f5207b7SJohn Levon static void vrfy_bb_in_list(struct basic_block *bb, struct basic_block_list *list) 868*1f5207b7SJohn Levon { 869*1f5207b7SJohn Levon if (bb) { 870*1f5207b7SJohn Levon struct basic_block *tmp; 871*1f5207b7SJohn Levon int no_bb_in_list = 0; 872*1f5207b7SJohn Levon 873*1f5207b7SJohn Levon FOR_EACH_PTR(list, tmp) { 874*1f5207b7SJohn Levon if (bb == tmp) 875*1f5207b7SJohn Levon return; 876*1f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 877*1f5207b7SJohn Levon assert(no_bb_in_list); 878*1f5207b7SJohn Levon } 879*1f5207b7SJohn Levon } 880*1f5207b7SJohn Levon 881*1f5207b7SJohn Levon static void vrfy_parents(struct basic_block *bb) 882*1f5207b7SJohn Levon { 883*1f5207b7SJohn Levon struct basic_block *tmp; 884*1f5207b7SJohn Levon FOR_EACH_PTR(bb->parents, tmp) { 885*1f5207b7SJohn Levon vrfy_bb_in_list(bb, tmp->children); 886*1f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 887*1f5207b7SJohn Levon } 888*1f5207b7SJohn Levon 889*1f5207b7SJohn Levon static void vrfy_children(struct basic_block *bb) 890*1f5207b7SJohn Levon { 891*1f5207b7SJohn Levon struct basic_block *tmp; 892*1f5207b7SJohn Levon struct instruction *br = last_instruction(bb->insns); 893*1f5207b7SJohn Levon 894*1f5207b7SJohn Levon if (!br) { 895*1f5207b7SJohn Levon assert(!bb->children); 896*1f5207b7SJohn Levon return; 897*1f5207b7SJohn Levon } 898*1f5207b7SJohn Levon switch (br->opcode) { 899*1f5207b7SJohn Levon struct multijmp *jmp; 900*1f5207b7SJohn Levon case OP_CBR: 901*1f5207b7SJohn Levon vrfy_bb_in_list(br->bb_false, bb->children); 902*1f5207b7SJohn Levon /* fall through */ 903*1f5207b7SJohn Levon case OP_BR: 904*1f5207b7SJohn Levon vrfy_bb_in_list(br->bb_true, bb->children); 905*1f5207b7SJohn Levon break; 906*1f5207b7SJohn Levon case OP_SWITCH: 907*1f5207b7SJohn Levon case OP_COMPUTEDGOTO: 908*1f5207b7SJohn Levon FOR_EACH_PTR(br->multijmp_list, jmp) { 909*1f5207b7SJohn Levon vrfy_bb_in_list(jmp->target, bb->children); 910*1f5207b7SJohn Levon } END_FOR_EACH_PTR(jmp); 911*1f5207b7SJohn Levon break; 912*1f5207b7SJohn Levon default: 913*1f5207b7SJohn Levon break; 914*1f5207b7SJohn Levon } 915*1f5207b7SJohn Levon 916*1f5207b7SJohn Levon FOR_EACH_PTR(bb->children, tmp) { 917*1f5207b7SJohn Levon vrfy_bb_in_list(bb, tmp->parents); 918*1f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 919*1f5207b7SJohn Levon } 920*1f5207b7SJohn Levon 921*1f5207b7SJohn Levon static void vrfy_bb_flow(struct basic_block *bb) 922*1f5207b7SJohn Levon { 923*1f5207b7SJohn Levon vrfy_children(bb); 924*1f5207b7SJohn Levon vrfy_parents(bb); 925*1f5207b7SJohn Levon } 926*1f5207b7SJohn Levon 927*1f5207b7SJohn Levon void vrfy_flow(struct entrypoint *ep) 928*1f5207b7SJohn Levon { 929*1f5207b7SJohn Levon struct basic_block *bb; 930*1f5207b7SJohn Levon struct basic_block *entry = ep->entry->bb; 931*1f5207b7SJohn Levon 932*1f5207b7SJohn Levon FOR_EACH_PTR(ep->bbs, bb) { 933*1f5207b7SJohn Levon if (bb == entry) 934*1f5207b7SJohn Levon entry = NULL; 935*1f5207b7SJohn Levon vrfy_bb_flow(bb); 936*1f5207b7SJohn Levon } END_FOR_EACH_PTR(bb); 937*1f5207b7SJohn Levon assert(!entry); 938*1f5207b7SJohn Levon } 939*1f5207b7SJohn Levon 940*1f5207b7SJohn Levon void pack_basic_blocks(struct entrypoint *ep) 941*1f5207b7SJohn Levon { 942*1f5207b7SJohn Levon struct basic_block *bb; 943*1f5207b7SJohn Levon 944*1f5207b7SJohn Levon /* See if we can merge a bb into another one.. */ 945*1f5207b7SJohn Levon FOR_EACH_PTR(ep->bbs, bb) { 946*1f5207b7SJohn Levon struct instruction *first, *insn; 947*1f5207b7SJohn Levon struct basic_block *parent, *child, *last; 948*1f5207b7SJohn Levon 949*1f5207b7SJohn Levon if (!bb_reachable(bb)) 950*1f5207b7SJohn Levon continue; 951*1f5207b7SJohn Levon 952*1f5207b7SJohn Levon /* 953*1f5207b7SJohn Levon * Just a branch? 954*1f5207b7SJohn Levon */ 955*1f5207b7SJohn Levon FOR_EACH_PTR(bb->insns, first) { 956*1f5207b7SJohn Levon if (!first->bb) 957*1f5207b7SJohn Levon continue; 958*1f5207b7SJohn Levon switch (first->opcode) { 959*1f5207b7SJohn Levon case OP_NOP: case OP_LNOP: case OP_SNOP: 960*1f5207b7SJohn Levon continue; 961*1f5207b7SJohn Levon case OP_CBR: 962*1f5207b7SJohn Levon case OP_BR: { 963*1f5207b7SJohn Levon struct basic_block *replace; 964*1f5207b7SJohn Levon replace = rewrite_branch_bb(bb, first); 965*1f5207b7SJohn Levon if (replace) { 966*1f5207b7SJohn Levon kill_bb(bb); 967*1f5207b7SJohn Levon goto no_merge; 968*1f5207b7SJohn Levon } 969*1f5207b7SJohn Levon } 970*1f5207b7SJohn Levon /* fallthrough */ 971*1f5207b7SJohn Levon default: 972*1f5207b7SJohn Levon goto out; 973*1f5207b7SJohn Levon } 974*1f5207b7SJohn Levon } END_FOR_EACH_PTR(first); 975*1f5207b7SJohn Levon 976*1f5207b7SJohn Levon out: 977*1f5207b7SJohn Levon /* 978*1f5207b7SJohn Levon * See if we only have one parent.. 979*1f5207b7SJohn Levon */ 980*1f5207b7SJohn Levon last = NULL; 981*1f5207b7SJohn Levon FOR_EACH_PTR(bb->parents, parent) { 982*1f5207b7SJohn Levon if (last) { 983*1f5207b7SJohn Levon if (last != parent) 984*1f5207b7SJohn Levon goto no_merge; 985*1f5207b7SJohn Levon continue; 986*1f5207b7SJohn Levon } 987*1f5207b7SJohn Levon last = parent; 988*1f5207b7SJohn Levon } END_FOR_EACH_PTR(parent); 989*1f5207b7SJohn Levon 990*1f5207b7SJohn Levon parent = last; 991*1f5207b7SJohn Levon if (!parent || parent == bb) 992*1f5207b7SJohn Levon continue; 993*1f5207b7SJohn Levon 994*1f5207b7SJohn Levon /* 995*1f5207b7SJohn Levon * Goodie. See if the parent can merge.. 996*1f5207b7SJohn Levon */ 997*1f5207b7SJohn Levon FOR_EACH_PTR(parent->children, child) { 998*1f5207b7SJohn Levon if (child != bb) 999*1f5207b7SJohn Levon goto no_merge; 1000*1f5207b7SJohn Levon } END_FOR_EACH_PTR(child); 1001*1f5207b7SJohn Levon 1002*1f5207b7SJohn Levon /* 1003*1f5207b7SJohn Levon * Merge the two. 1004*1f5207b7SJohn Levon */ 1005*1f5207b7SJohn Levon repeat_phase |= REPEAT_CSE; 1006*1f5207b7SJohn Levon 1007*1f5207b7SJohn Levon parent->children = bb->children; 1008*1f5207b7SJohn Levon bb->children = NULL; 1009*1f5207b7SJohn Levon bb->parents = NULL; 1010*1f5207b7SJohn Levon 1011*1f5207b7SJohn Levon FOR_EACH_PTR(parent->children, child) { 1012*1f5207b7SJohn Levon replace_bb_in_list(&child->parents, bb, parent, 0); 1013*1f5207b7SJohn Levon } END_FOR_EACH_PTR(child); 1014*1f5207b7SJohn Levon 1015*1f5207b7SJohn Levon kill_instruction(delete_last_instruction(&parent->insns)); 1016*1f5207b7SJohn Levon FOR_EACH_PTR(bb->insns, insn) { 1017*1f5207b7SJohn Levon if (insn->bb) { 1018*1f5207b7SJohn Levon assert(insn->bb == bb); 1019*1f5207b7SJohn Levon insn->bb = parent; 1020*1f5207b7SJohn Levon } 1021*1f5207b7SJohn Levon add_instruction(&parent->insns, insn); 1022*1f5207b7SJohn Levon } END_FOR_EACH_PTR(insn); 1023*1f5207b7SJohn Levon bb->insns = NULL; 1024*1f5207b7SJohn Levon 1025*1f5207b7SJohn Levon no_merge: 1026*1f5207b7SJohn Levon /* nothing to do */; 1027*1f5207b7SJohn Levon } END_FOR_EACH_PTR(bb); 1028*1f5207b7SJohn Levon } 1029*1f5207b7SJohn Levon 1030*1f5207b7SJohn Levon 1031